1
/*!
2
This module provides a regular expression parser.
3
*/
4

            
5
use core::{
6
    borrow::Borrow,
7
    cell::{Cell, RefCell},
8
    mem,
9
};
10

            
11
use alloc::{
12
    boxed::Box,
13
    string::{String, ToString},
14
    vec,
15
    vec::Vec,
16
};
17

            
18
use crate::{
19
    ast::{self, Ast, Position, Span},
20
    either::Either,
21
    is_escapeable_character, is_meta_character,
22
};
23

            
24
type Result<T> = core::result::Result<T, ast::Error>;
25

            
26
/// A primitive is an expression with no sub-expressions. This includes
27
/// literals, assertions and non-set character classes. This representation
28
/// is used as intermediate state in the parser.
29
///
30
/// This does not include ASCII character classes, since they can only appear
31
/// within a set character class.
32
#[derive(Clone, Debug, Eq, PartialEq)]
33
enum Primitive {
34
    Literal(ast::Literal),
35
    Assertion(ast::Assertion),
36
    Dot(Span),
37
    Perl(ast::ClassPerl),
38
    Unicode(ast::ClassUnicode),
39
}
40

            
41
impl Primitive {
42
    /// Return the span of this primitive.
43
8
    fn span(&self) -> &Span {
44
8
        match *self {
45
8
            Primitive::Literal(ref x) => &x.span,
46
            Primitive::Assertion(ref x) => &x.span,
47
            Primitive::Dot(ref span) => span,
48
            Primitive::Perl(ref x) => &x.span,
49
            Primitive::Unicode(ref x) => &x.span,
50
        }
51
8
    }
52

            
53
    /// Convert this primitive into a proper AST.
54
118
    fn into_ast(self) -> Ast {
55
118
        match self {
56
110
            Primitive::Literal(lit) => Ast::literal(lit),
57
8
            Primitive::Assertion(assert) => Ast::assertion(assert),
58
            Primitive::Dot(span) => Ast::dot(span),
59
            Primitive::Perl(cls) => Ast::class_perl(cls),
60
            Primitive::Unicode(cls) => Ast::class_unicode(cls),
61
        }
62
118
    }
63

            
64
    /// Convert this primitive into an item in a character class.
65
    ///
66
    /// If this primitive is not a legal item (i.e., an assertion or a dot),
67
    /// then return an error.
68
8
    fn into_class_set_item<P: Borrow<Parser>>(
69
8
        self,
70
8
        p: &ParserI<'_, P>,
71
8
    ) -> Result<ast::ClassSetItem> {
72
        use self::Primitive::*;
73
        use crate::ast::ClassSetItem;
74

            
75
8
        match self {
76
6
            Literal(lit) => Ok(ClassSetItem::Literal(lit)),
77
2
            Perl(cls) => Ok(ClassSetItem::Perl(cls)),
78
            Unicode(cls) => Ok(ClassSetItem::Unicode(cls)),
79
            x => Err(p.error(*x.span(), ast::ErrorKind::ClassEscapeInvalid)),
80
        }
81
8
    }
82

            
83
    /// Convert this primitive into a literal in a character class. In
84
    /// particular, literals are the only valid items that can appear in
85
    /// ranges.
86
    ///
87
    /// If this primitive is not a legal item (i.e., a class, assertion or a
88
    /// dot), then return an error.
89
8
    fn into_class_literal<P: Borrow<Parser>>(
90
8
        self,
91
8
        p: &ParserI<'_, P>,
92
8
    ) -> Result<ast::Literal> {
93
        use self::Primitive::*;
94

            
95
8
        match self {
96
8
            Literal(lit) => Ok(lit),
97
            x => Err(p.error(*x.span(), ast::ErrorKind::ClassRangeLiteral)),
98
        }
99
8
    }
100
}
101

            
102
/// Returns true if the given character is a hexadecimal digit.
103
fn is_hex(c: char) -> bool {
104
    ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') || ('A' <= c && c <= 'F')
105
}
106

            
107
/// Returns true if the given character is a valid in a capture group name.
108
///
109
/// If `first` is true, then `c` is treated as the first character in the
110
/// group name (which must be alphabetic or underscore).
111
54
fn is_capture_char(c: char, first: bool) -> bool {
112
54
    if first {
113
8
        c == '_' || c.is_alphabetic()
114
    } else {
115
46
        c == '_' || c == '.' || c == '[' || c == ']' || c.is_alphanumeric()
116
    }
117
54
}
118

            
119
/// A builder for a regular expression parser.
120
///
121
/// This builder permits modifying configuration options for the parser.
122
#[derive(Clone, Debug)]
123
pub struct ParserBuilder {
124
    ignore_whitespace: bool,
125
    nest_limit: u32,
126
    octal: bool,
127
}
128

            
129
impl Default for ParserBuilder {
130
16
    fn default() -> ParserBuilder {
131
16
        ParserBuilder::new()
132
16
    }
133
}
134

            
135
impl ParserBuilder {
136
    /// Create a new parser builder with a default configuration.
137
18
    pub fn new() -> ParserBuilder {
138
18
        ParserBuilder {
139
18
            ignore_whitespace: false,
140
18
            nest_limit: 250,
141
18
            octal: false,
142
18
        }
143
18
    }
144

            
145
    /// Build a parser from this configuration with the given pattern.
146
2
    pub fn build(&self) -> Parser {
147
2
        Parser {
148
2
            pos: Cell::new(Position { offset: 0, line: 1, column: 1 }),
149
2
            capture_index: Cell::new(0),
150
2
            nest_limit: self.nest_limit,
151
2
            octal: self.octal,
152
2
            initial_ignore_whitespace: self.ignore_whitespace,
153
2
            ignore_whitespace: Cell::new(self.ignore_whitespace),
154
2
            comments: RefCell::new(vec![]),
155
2
            stack_group: RefCell::new(vec![]),
156
2
            stack_class: RefCell::new(vec![]),
157
2
            capture_names: RefCell::new(vec![]),
158
2
            scratch: RefCell::new(String::new()),
159
2
        }
160
2
    }
161

            
162
    /// Set the nesting limit for this parser.
163
    ///
164
    /// The nesting limit controls how deep the abstract syntax tree is allowed
165
    /// to be. If the AST exceeds the given limit (e.g., with too many nested
166
    /// groups), then an error is returned by the parser.
167
    ///
168
    /// The purpose of this limit is to act as a heuristic to prevent stack
169
    /// overflow for consumers that do structural induction on an `Ast` using
170
    /// explicit recursion. While this crate never does this (instead using
171
    /// constant stack space and moving the call stack to the heap), other
172
    /// crates may.
173
    ///
174
    /// This limit is not checked until the entire AST is parsed. Therefore,
175
    /// if callers want to put a limit on the amount of heap space used, then
176
    /// they should impose a limit on the length, in bytes, of the concrete
177
    /// pattern string. In particular, this is viable since this parser
178
    /// implementation will limit itself to heap space proportional to the
179
    /// length of the pattern string.
180
    ///
181
    /// Note that a nest limit of `0` will return a nest limit error for most
182
    /// patterns but not all. For example, a nest limit of `0` permits `a` but
183
    /// not `ab`, since `ab` requires a concatenation, which results in a nest
184
    /// depth of `1`. In general, a nest limit is not something that manifests
185
    /// in an obvious way in the concrete syntax, therefore, it should not be
186
    /// used in a granular way.
187
2
    pub fn nest_limit(&mut self, limit: u32) -> &mut ParserBuilder {
188
2
        self.nest_limit = limit;
189
2
        self
190
2
    }
191

            
192
    /// Whether to support octal syntax or not.
193
    ///
194
    /// Octal syntax is a little-known way of uttering Unicode codepoints in
195
    /// a regular expression. For example, `a`, `\x61`, `\u0061` and
196
    /// `\141` are all equivalent regular expressions, where the last example
197
    /// shows octal syntax.
198
    ///
199
    /// While supporting octal syntax isn't in and of itself a problem, it does
200
    /// make good error messages harder. That is, in PCRE based regex engines,
201
    /// syntax like `\0` invokes a backreference, which is explicitly
202
    /// unsupported in Rust's regex engine. However, many users expect it to
203
    /// be supported. Therefore, when octal support is disabled, the error
204
    /// message will explicitly mention that backreferences aren't supported.
205
    ///
206
    /// Octal syntax is disabled by default.
207
2
    pub fn octal(&mut self, yes: bool) -> &mut ParserBuilder {
208
2
        self.octal = yes;
209
2
        self
210
2
    }
211

            
212
    /// Enable verbose mode in the regular expression.
213
    ///
214
    /// When enabled, verbose mode permits insignificant whitespace in many
215
    /// places in the regular expression, as well as comments. Comments are
216
    /// started using `#` and continue until the end of the line.
217
    ///
218
    /// By default, this is disabled. It may be selectively enabled in the
219
    /// regular expression by using the `x` flag regardless of this setting.
220
2
    pub fn ignore_whitespace(&mut self, yes: bool) -> &mut ParserBuilder {
221
2
        self.ignore_whitespace = yes;
222
2
        self
223
2
    }
224
}
225

            
226
/// A regular expression parser.
227
///
228
/// This parses a string representation of a regular expression into an
229
/// abstract syntax tree. The size of the tree is proportional to the length
230
/// of the regular expression pattern.
231
///
232
/// A `Parser` can be configured in more detail via a [`ParserBuilder`].
233
#[derive(Clone, Debug)]
234
pub struct Parser {
235
    /// The current position of the parser.
236
    pos: Cell<Position>,
237
    /// The current capture index.
238
    capture_index: Cell<u32>,
239
    /// The maximum number of open parens/brackets allowed. If the parser
240
    /// exceeds this number, then an error is returned.
241
    nest_limit: u32,
242
    /// Whether to support octal syntax or not. When `false`, the parser will
243
    /// return an error helpfully pointing out that backreferences are not
244
    /// supported.
245
    octal: bool,
246
    /// The initial setting for `ignore_whitespace` as provided by
247
    /// `ParserBuilder`. It is used when resetting the parser's state.
248
    initial_ignore_whitespace: bool,
249
    /// Whether whitespace should be ignored. When enabled, comments are
250
    /// also permitted.
251
    ignore_whitespace: Cell<bool>,
252
    /// A list of comments, in order of appearance.
253
    comments: RefCell<Vec<ast::Comment>>,
254
    /// A stack of grouped sub-expressions, including alternations.
255
    stack_group: RefCell<Vec<GroupState>>,
256
    /// A stack of nested character classes. This is only non-empty when
257
    /// parsing a class.
258
    stack_class: RefCell<Vec<ClassState>>,
259
    /// A sorted sequence of capture names. This is used to detect duplicate
260
    /// capture names and report an error if one is detected.
261
    capture_names: RefCell<Vec<ast::CaptureName>>,
262
    /// A scratch buffer used in various places. Mostly this is used to
263
    /// accumulate relevant characters from parts of a pattern.
264
    scratch: RefCell<String>,
265
}
266

            
267
/// ParserI is the internal parser implementation.
268
///
269
/// We use this separate type so that we can carry the provided pattern string
270
/// along with us. In particular, a `Parser` internal state is not tied to any
271
/// one pattern, but `ParserI` is.
272
///
273
/// This type also lets us use `ParserI<&Parser>` in production code while
274
/// retaining the convenience of `ParserI<Parser>` for tests, which sometimes
275
/// work against the internal interface of the parser.
276
#[derive(Clone, Debug)]
277
struct ParserI<'s, P> {
278
    /// The parser state/configuration.
279
    parser: P,
280
    /// The full regular expression provided by the user.
281
    pattern: &'s str,
282
}
283

            
284
/// GroupState represents a single stack frame while parsing nested groups
285
/// and alternations. Each frame records the state up to an opening parenthesis
286
/// or a alternating bracket `|`.
287
#[derive(Clone, Debug)]
288
enum GroupState {
289
    /// This state is pushed whenever an opening group is found.
290
    Group {
291
        /// The concatenation immediately preceding the opening group.
292
        concat: ast::Concat,
293
        /// The group that has been opened. Its sub-AST is always empty.
294
        group: ast::Group,
295
        /// Whether this group has the `x` flag enabled or not.
296
        ignore_whitespace: bool,
297
    },
298
    /// This state is pushed whenever a new alternation branch is found. If
299
    /// an alternation branch is found and this state is at the top of the
300
    /// stack, then this state should be modified to include the new
301
    /// alternation.
302
    Alternation(ast::Alternation),
303
}
304

            
305
/// ClassState represents a single stack frame while parsing character classes.
306
/// Each frame records the state up to an intersection, difference, symmetric
307
/// difference or nested class.
308
///
309
/// Note that a parser's character class stack is only non-empty when parsing
310
/// a character class. In all other cases, it is empty.
311
#[derive(Clone, Debug)]
312
enum ClassState {
313
    /// This state is pushed whenever an opening bracket is found.
314
    Open {
315
        /// The union of class items immediately preceding this class.
316
        union: ast::ClassSetUnion,
317
        /// The class that has been opened. Typically this just corresponds
318
        /// to the `[`, but it can also include `[^` since `^` indicates
319
        /// negation of the class.
320
        set: ast::ClassBracketed,
321
    },
322
    /// This state is pushed when a operator is seen. When popped, the stored
323
    /// set becomes the left hand side of the operator.
324
    Op {
325
        /// The type of the operation, i.e., &&, -- or ~~.
326
        kind: ast::ClassSetBinaryOpKind,
327
        /// The left-hand side of the operator.
328
        lhs: ast::ClassSet,
329
    },
330
}
331

            
332
impl Parser {
333
    /// Create a new parser with a default configuration.
334
    ///
335
    /// The parser can be run with either the `parse` or `parse_with_comments`
336
    /// methods. The parse methods return an abstract syntax tree.
337
    ///
338
    /// To set configuration options on the parser, use [`ParserBuilder`].
339
    pub fn new() -> Parser {
340
        ParserBuilder::new().build()
341
    }
342

            
343
    /// Parse the regular expression into an abstract syntax tree.
344
2
    pub fn parse(&mut self, pattern: &str) -> Result<Ast> {
345
2
        ParserI::new(self, pattern).parse()
346
2
    }
347

            
348
    /// Parse the regular expression and return an abstract syntax tree with
349
    /// all of the comments found in the pattern.
350
    pub fn parse_with_comments(
351
        &mut self,
352
        pattern: &str,
353
    ) -> Result<ast::WithComments> {
354
        ParserI::new(self, pattern).parse_with_comments()
355
    }
356

            
357
    /// Reset the internal state of a parser.
358
    ///
359
    /// This is called at the beginning of every parse. This prevents the
360
    /// parser from running with inconsistent state (say, if a previous
361
    /// invocation returned an error and the parser is reused).
362
2
    fn reset(&self) {
363
2
        // These settings should be in line with the construction
364
2
        // in `ParserBuilder::build`.
365
2
        self.pos.set(Position { offset: 0, line: 1, column: 1 });
366
2
        self.ignore_whitespace.set(self.initial_ignore_whitespace);
367
2
        self.comments.borrow_mut().clear();
368
2
        self.stack_group.borrow_mut().clear();
369
2
        self.stack_class.borrow_mut().clear();
370
2
    }
371
}
372

            
373
impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
374
    /// Build an internal parser from a parser configuration and a pattern.
375
2
    fn new(parser: P, pattern: &'s str) -> ParserI<'s, P> {
376
2
        ParserI { parser, pattern }
377
2
    }
378

            
379
    /// Return a reference to the parser state.
380
12990
    fn parser(&self) -> &Parser {
381
12990
        self.parser.borrow()
382
12990
    }
383

            
384
    /// Return a reference to the pattern being parsed.
385
9030
    fn pattern(&self) -> &str {
386
9030
        self.pattern
387
9030
    }
388

            
389
    /// Create a new error with the given span and error type.
390
    fn error(&self, span: Span, kind: ast::ErrorKind) -> ast::Error {
391
        ast::Error { kind, pattern: self.pattern().to_string(), span }
392
    }
393

            
394
    /// Return the current offset of the parser.
395
    ///
396
    /// The offset starts at `0` from the beginning of the regular expression
397
    /// pattern string.
398
9166
    fn offset(&self) -> usize {
399
9166
        self.parser().pos.get().offset
400
9166
    }
401

            
402
    /// Return the current line number of the parser.
403
    ///
404
    /// The line number starts at `1`.
405
152
    fn line(&self) -> usize {
406
152
        self.parser().pos.get().line
407
152
    }
408

            
409
    /// Return the current column of the parser.
410
    ///
411
    /// The column number starts at `1` and is reset whenever a `\n` is seen.
412
152
    fn column(&self) -> usize {
413
152
        self.parser().pos.get().column
414
152
    }
415

            
416
    /// Return the next capturing index. Each subsequent call increments the
417
    /// internal index.
418
    ///
419
    /// The span given should correspond to the location of the opening
420
    /// parenthesis.
421
    ///
422
    /// If the capture limit is exceeded, then an error is returned.
423
8
    fn next_capture_index(&self, span: Span) -> Result<u32> {
424
8
        let current = self.parser().capture_index.get();
425
8
        let i = current.checked_add(1).ok_or_else(|| {
426
            self.error(span, ast::ErrorKind::CaptureLimitExceeded)
427
8
        })?;
428
8
        self.parser().capture_index.set(i);
429
8
        Ok(i)
430
8
    }
431

            
432
    /// Adds the given capture name to this parser. If this capture name has
433
    /// already been used, then an error is returned.
434
8
    fn add_capture_name(&self, cap: &ast::CaptureName) -> Result<()> {
435
8
        let mut names = self.parser().capture_names.borrow_mut();
436
8
        match names
437
10
            .binary_search_by_key(&cap.name.as_str(), |c| c.name.as_str())
438
        {
439
8
            Err(i) => {
440
8
                names.insert(i, cap.clone());
441
8
                Ok(())
442
            }
443
            Ok(i) => Err(self.error(
444
                cap.span,
445
                ast::ErrorKind::GroupNameDuplicate { original: names[i].span },
446
            )),
447
        }
448
8
    }
449

            
450
    /// Return whether the parser should ignore whitespace or not.
451
308
    fn ignore_whitespace(&self) -> bool {
452
308
        self.parser().ignore_whitespace.get()
453
308
    }
454

            
455
    /// Return the character at the current position of the parser.
456
    ///
457
    /// This panics if the current position does not point to a valid char.
458
4968
    fn char(&self) -> char {
459
4968
        self.char_at(self.offset())
460
4968
    }
461

            
462
    /// Return the character at the given position.
463
    ///
464
    /// This panics if the given position does not point to a valid char.
465
4968
    fn char_at(&self, i: usize) -> char {
466
4968
        self.pattern()[i..]
467
4968
            .chars()
468
4968
            .next()
469
4968
            .unwrap_or_else(|| panic!("expected char at offset {}", i))
470
4968
    }
471

            
472
    /// Bump the parser to the next Unicode scalar value.
473
    ///
474
    /// If the end of the input has been reached, then `false` is returned.
475
1226
    fn bump(&self) -> bool {
476
1226
        if self.is_eof() {
477
            return false;
478
1226
        }
479
1226
        let Position { mut offset, mut line, mut column } = self.pos();
480
1226
        if self.char() == '\n' {
481
28
            line = line.checked_add(1).unwrap();
482
28
            column = 1;
483
1198
        } else {
484
1198
            column = column.checked_add(1).unwrap();
485
1198
        }
486
1226
        offset += self.char().len_utf8();
487
1226
        self.parser().pos.set(Position { offset, line, column });
488
1226
        self.pattern()[self.offset()..].chars().next().is_some()
489
1226
    }
490

            
491
    /// If the substring starting at the current position of the parser has
492
    /// the given prefix, then bump the parser to the character immediately
493
    /// following the prefix and return true. Otherwise, don't bump the parser
494
    /// and return false.
495
110
    fn bump_if(&self, prefix: &str) -> bool {
496
110
        if self.pattern()[self.offset()..].starts_with(prefix) {
497
34
            for _ in 0..prefix.chars().count() {
498
34
                self.bump();
499
34
            }
500
18
            true
501
        } else {
502
92
            false
503
        }
504
110
    }
505

            
506
    /// Returns true if and only if the parser is positioned at a look-around
507
    /// prefix. The conditions under which this returns true must always
508
    /// correspond to a regular expression that would otherwise be consider
509
    /// invalid.
510
    ///
511
    /// This should only be called immediately after parsing the opening of
512
    /// a group or a set of flags.
513
18
    fn is_lookaround_prefix(&self) -> bool {
514
18
        self.bump_if("?=")
515
18
            || self.bump_if("?!")
516
18
            || self.bump_if("?<=")
517
18
            || self.bump_if("?<!")
518
18
    }
519

            
520
    /// Bump the parser, and if the `x` flag is enabled, bump through any
521
    /// subsequent spaces. Return true if and only if the parser is not at
522
    /// EOF.
523
24
    fn bump_and_bump_space(&self) -> bool {
524
24
        if !self.bump() {
525
            return false;
526
24
        }
527
24
        self.bump_space();
528
24
        !self.is_eof()
529
24
    }
530

            
531
    /// If the `x` flag is enabled (i.e., whitespace insensitivity with
532
    /// comments), then this will advance the parser through all whitespace
533
    /// and comments to the next non-whitespace non-comment byte.
534
    ///
535
    /// If the `x` flag is disabled, then this is a no-op.
536
    ///
537
    /// This should be used selectively throughout the parser where
538
    /// arbitrary whitespace is permitted when the `x` flag is enabled. For
539
    /// example, `{   5  , 6}` is equivalent to `{5,6}`.
540
282
    fn bump_space(&self) {
541
282
        if !self.ignore_whitespace() {
542
4
            return;
543
278
        }
544
712
        while !self.is_eof() {
545
710
            if self.char().is_whitespace() {
546
422
                self.bump();
547
422
            } else if self.char() == '#' {
548
12
                let start = self.pos();
549
12
                let mut comment_text = String::new();
550
12
                self.bump();
551
436
                while !self.is_eof() {
552
436
                    let c = self.char();
553
436
                    self.bump();
554
436
                    if c == '\n' {
555
12
                        break;
556
424
                    }
557
424
                    comment_text.push(c);
558
                }
559
12
                let comment = ast::Comment {
560
12
                    span: Span::new(start, self.pos()),
561
12
                    comment: comment_text,
562
12
                };
563
12
                self.parser().comments.borrow_mut().push(comment);
564
            } else {
565
276
                break;
566
            }
567
        }
568
282
    }
569

            
570
    /// Peek at the next character in the input without advancing the parser.
571
    ///
572
    /// If the input has been exhausted, then this returns `None`.
573
2
    fn peek(&self) -> Option<char> {
574
2
        if self.is_eof() {
575
            return None;
576
2
        }
577
2
        self.pattern()[self.offset() + self.char().len_utf8()..].chars().next()
578
2
    }
579

            
580
    /// Like peek, but will ignore spaces when the parser is in whitespace
581
    /// insensitive mode.
582
10
    fn peek_space(&self) -> Option<char> {
583
10
        if !self.ignore_whitespace() {
584
            return self.peek();
585
10
        }
586
10
        if self.is_eof() {
587
            return None;
588
10
        }
589
10
        let mut start = self.offset() + self.char().len_utf8();
590
10
        let mut in_comment = false;
591
10
        for (i, c) in self.pattern()[start..].char_indices() {
592
10
            if c.is_whitespace() {
593
                continue;
594
10
            } else if !in_comment && c == '#' {
595
                in_comment = true;
596
10
            } else if in_comment && c == '\n' {
597
                in_comment = false;
598
            } else {
599
10
                start += i;
600
10
                break;
601
            }
602
        }
603
10
        self.pattern()[start..].chars().next()
604
10
    }
605

            
606
    /// Returns true if the next call to `bump` would return false.
607
2696
    fn is_eof(&self) -> bool {
608
2696
        self.offset() == self.pattern().len()
609
2696
    }
610

            
611
    /// Return the current position of the parser, which includes the offset,
612
    /// line and column.
613
1738
    fn pos(&self) -> Position {
614
1738
        self.parser().pos.get()
615
1738
    }
616

            
617
    /// Create a span at the current position of the parser. Both the start
618
    /// and end of the span are set.
619
106
    fn span(&self) -> Span {
620
106
        Span::splat(self.pos())
621
106
    }
622

            
623
    /// Create a span that covers the current character.
624
152
    fn span_char(&self) -> Span {
625
152
        let mut next = Position {
626
152
            offset: self.offset().checked_add(self.char().len_utf8()).unwrap(),
627
152
            line: self.line(),
628
152
            column: self.column().checked_add(1).unwrap(),
629
152
        };
630
152
        if self.char() == '\n' {
631
            next.line += 1;
632
            next.column = 1;
633
152
        }
634
152
        Span::new(self.pos(), next)
635
152
    }
636

            
637
    /// Parse and push a single alternation on to the parser's internal stack.
638
    /// If the top of the stack already has an alternation, then add to that
639
    /// instead of pushing a new one.
640
    ///
641
    /// The concatenation given corresponds to a single alternation branch.
642
    /// The concatenation returned starts the next branch and is empty.
643
    ///
644
    /// This assumes the parser is currently positioned at `|` and will advance
645
    /// the parser to the character following `|`.
646
    #[inline(never)]
647
28
    fn push_alternate(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
648
28
        assert_eq!(self.char(), '|');
649
28
        concat.span.end = self.pos();
650
28
        self.push_or_add_alternation(concat);
651
28
        self.bump();
652
28
        Ok(ast::Concat { span: self.span(), asts: vec![] })
653
28
    }
654

            
655
    /// Pushes or adds the given branch of an alternation to the parser's
656
    /// internal stack of state.
657
28
    fn push_or_add_alternation(&self, concat: ast::Concat) {
658
        use self::GroupState::*;
659

            
660
28
        let mut stack = self.parser().stack_group.borrow_mut();
661
28
        if let Some(&mut Alternation(ref mut alts)) = stack.last_mut() {
662
20
            alts.asts.push(concat.into_ast());
663
20
            return;
664
8
        }
665
8
        stack.push(Alternation(ast::Alternation {
666
8
            span: Span::new(concat.span.start, self.pos()),
667
8
            asts: vec![concat.into_ast()],
668
8
        }));
669
28
    }
670

            
671
    /// Parse and push a group AST (and its parent concatenation) on to the
672
    /// parser's internal stack. Return a fresh concatenation corresponding
673
    /// to the group's sub-AST.
674
    ///
675
    /// If a set of flags was found (with no group), then the concatenation
676
    /// is returned with that set of flags added.
677
    ///
678
    /// This assumes that the parser is currently positioned on the opening
679
    /// parenthesis. It advances the parser to the character at the start
680
    /// of the sub-expression (or adjoining expression).
681
    ///
682
    /// If there was a problem parsing the start of the group, then an error
683
    /// is returned.
684
    #[inline(never)]
685
18
    fn push_group(&self, mut concat: ast::Concat) -> Result<ast::Concat> {
686
18
        assert_eq!(self.char(), '(');
687
18
        match self.parse_group()? {
688
2
            Either::Left(set) => {
689
2
                let ignore = set.flags.flag_state(ast::Flag::IgnoreWhitespace);
690
2
                if let Some(v) = ignore {
691
2
                    self.parser().ignore_whitespace.set(v);
692
2
                }
693

            
694
2
                concat.asts.push(Ast::flags(set));
695
2
                Ok(concat)
696
            }
697
16
            Either::Right(group) => {
698
16
                let old_ignore_whitespace = self.ignore_whitespace();
699
16
                let new_ignore_whitespace = group
700
16
                    .flags()
701
16
                    .and_then(|f| f.flag_state(ast::Flag::IgnoreWhitespace))
702
16
                    .unwrap_or(old_ignore_whitespace);
703
16
                self.parser().stack_group.borrow_mut().push(
704
16
                    GroupState::Group {
705
16
                        concat,
706
16
                        group,
707
16
                        ignore_whitespace: old_ignore_whitespace,
708
16
                    },
709
16
                );
710
16
                self.parser().ignore_whitespace.set(new_ignore_whitespace);
711
16
                Ok(ast::Concat { span: self.span(), asts: vec![] })
712
            }
713
        }
714
18
    }
715

            
716
    /// Pop a group AST from the parser's internal stack and set the group's
717
    /// AST to the given concatenation. Return the concatenation containing
718
    /// the group.
719
    ///
720
    /// This assumes that the parser is currently positioned on the closing
721
    /// parenthesis and advances the parser to the character following the `)`.
722
    ///
723
    /// If no such group could be popped, then an unopened group error is
724
    /// returned.
725
    #[inline(never)]
726
16
    fn pop_group(&self, mut group_concat: ast::Concat) -> Result<ast::Concat> {
727
        use self::GroupState::*;
728

            
729
16
        assert_eq!(self.char(), ')');
730
16
        let mut stack = self.parser().stack_group.borrow_mut();
731
16
        let (mut prior_concat, mut group, ignore_whitespace, alt) = match stack
732
16
            .pop()
733
        {
734
10
            Some(Group { concat, group, ignore_whitespace }) => {
735
10
                (concat, group, ignore_whitespace, None)
736
            }
737
6
            Some(Alternation(alt)) => match stack.pop() {
738
6
                Some(Group { concat, group, ignore_whitespace }) => {
739
6
                    (concat, group, ignore_whitespace, Some(alt))
740
                }
741
                None | Some(Alternation(_)) => {
742
                    return Err(self.error(
743
                        self.span_char(),
744
                        ast::ErrorKind::GroupUnopened,
745
                    ));
746
                }
747
            },
748
            None => {
749
                return Err(self
750
                    .error(self.span_char(), ast::ErrorKind::GroupUnopened));
751
            }
752
        };
753
16
        self.parser().ignore_whitespace.set(ignore_whitespace);
754
16
        group_concat.span.end = self.pos();
755
16
        self.bump();
756
16
        group.span.end = self.pos();
757
16
        match alt {
758
6
            Some(mut alt) => {
759
6
                alt.span.end = group_concat.span.end;
760
6
                alt.asts.push(group_concat.into_ast());
761
6
                group.ast = Box::new(alt.into_ast());
762
6
            }
763
10
            None => {
764
10
                group.ast = Box::new(group_concat.into_ast());
765
10
            }
766
        }
767
16
        prior_concat.asts.push(Ast::group(group));
768
16
        Ok(prior_concat)
769
16
    }
770

            
771
    /// Pop the last state from the parser's internal stack, if it exists, and
772
    /// add the given concatenation to it. There either must be no state or a
773
    /// single alternation item on the stack. Any other scenario produces an
774
    /// error.
775
    ///
776
    /// This assumes that the parser has advanced to the end.
777
    #[inline(never)]
778
2
    fn pop_group_end(&self, mut concat: ast::Concat) -> Result<Ast> {
779
2
        concat.span.end = self.pos();
780
2
        let mut stack = self.parser().stack_group.borrow_mut();
781
2
        let ast = match stack.pop() {
782
            None => Ok(concat.into_ast()),
783
2
            Some(GroupState::Alternation(mut alt)) => {
784
2
                alt.span.end = self.pos();
785
2
                alt.asts.push(concat.into_ast());
786
2
                Ok(Ast::alternation(alt))
787
            }
788
            Some(GroupState::Group { group, .. }) => {
789
                return Err(
790
                    self.error(group.span, ast::ErrorKind::GroupUnclosed)
791
                );
792
            }
793
        };
794
        // If we try to pop again, there should be nothing.
795
2
        match stack.pop() {
796
2
            None => ast,
797
            Some(GroupState::Alternation(_)) => {
798
                // This unreachable is unfortunate. This case can't happen
799
                // because the only way we can be here is if there were two
800
                // `GroupState::Alternation`s adjacent in the parser's stack,
801
                // which we guarantee to never happen because we never push a
802
                // `GroupState::Alternation` if one is already at the top of
803
                // the stack.
804
                unreachable!()
805
            }
806
            Some(GroupState::Group { group, .. }) => {
807
                Err(self.error(group.span, ast::ErrorKind::GroupUnclosed))
808
            }
809
        }
810
2
    }
811

            
812
    /// Parse the opening of a character class and push the current class
813
    /// parsing context onto the parser's stack. This assumes that the parser
814
    /// is positioned at an opening `[`. The given union should correspond to
815
    /// the union of set items built up before seeing the `[`.
816
    ///
817
    /// If there was a problem parsing the opening of the class, then an error
818
    /// is returned. Otherwise, a new union of set items for the class is
819
    /// returned (which may be populated with either a `]` or a `-`).
820
    #[inline(never)]
821
8
    fn push_class_open(
822
8
        &self,
823
8
        parent_union: ast::ClassSetUnion,
824
8
    ) -> Result<ast::ClassSetUnion> {
825
8
        assert_eq!(self.char(), '[');
826

            
827
8
        let (nested_set, nested_union) = self.parse_set_class_open()?;
828
8
        self.parser()
829
8
            .stack_class
830
8
            .borrow_mut()
831
8
            .push(ClassState::Open { union: parent_union, set: nested_set });
832
8
        Ok(nested_union)
833
8
    }
834

            
835
    /// Parse the end of a character class set and pop the character class
836
    /// parser stack. The union given corresponds to the last union built
837
    /// before seeing the closing `]`. The union returned corresponds to the
838
    /// parent character class set with the nested class added to it.
839
    ///
840
    /// This assumes that the parser is positioned at a `]` and will advance
841
    /// the parser to the byte immediately following the `]`.
842
    ///
843
    /// If the stack is empty after popping, then this returns the final
844
    /// "top-level" character class AST (where a "top-level" character class
845
    /// is one that is not nested inside any other character class).
846
    ///
847
    /// If there is no corresponding opening bracket on the parser's stack,
848
    /// then an error is returned.
849
    #[inline(never)]
850
8
    fn pop_class(
851
8
        &self,
852
8
        nested_union: ast::ClassSetUnion,
853
8
    ) -> Result<Either<ast::ClassSetUnion, ast::ClassBracketed>> {
854
8
        assert_eq!(self.char(), ']');
855

            
856
8
        let item = ast::ClassSet::Item(nested_union.into_item());
857
8
        let prevset = self.pop_class_op(item);
858
8
        let mut stack = self.parser().stack_class.borrow_mut();
859
8
        match stack.pop() {
860
            None => {
861
                // We can never observe an empty stack:
862
                //
863
                // 1) We are guaranteed to start with a non-empty stack since
864
                //    the character class parser is only initiated when it sees
865
                //    a `[`.
866
                // 2) If we ever observe an empty stack while popping after
867
                //    seeing a `]`, then we signal the character class parser
868
                //    to terminate.
869
                panic!("unexpected empty character class stack")
870
            }
871
            Some(ClassState::Op { .. }) => {
872
                // This panic is unfortunate, but this case is impossible
873
                // since we already popped the Op state if one exists above.
874
                // Namely, every push to the class parser stack is guarded by
875
                // whether an existing Op is already on the top of the stack.
876
                // If it is, the existing Op is modified. That is, the stack
877
                // can never have consecutive Op states.
878
                panic!("unexpected ClassState::Op")
879
            }
880
8
            Some(ClassState::Open { mut union, mut set }) => {
881
8
                self.bump();
882
8
                set.span.end = self.pos();
883
8
                set.kind = prevset;
884
8
                if stack.is_empty() {
885
8
                    Ok(Either::Right(set))
886
                } else {
887
                    union.push(ast::ClassSetItem::Bracketed(Box::new(set)));
888
                    Ok(Either::Left(union))
889
                }
890
            }
891
        }
892
8
    }
893

            
894
    /// Return an "unclosed class" error whose span points to the most
895
    /// recently opened class.
896
    ///
897
    /// This should only be called while parsing a character class.
898
    #[inline(never)]
899
    fn unclosed_class_error(&self) -> ast::Error {
900
        for state in self.parser().stack_class.borrow().iter().rev() {
901
            if let ClassState::Open { ref set, .. } = *state {
902
                return self.error(set.span, ast::ErrorKind::ClassUnclosed);
903
            }
904
        }
905
        // We are guaranteed to have a non-empty stack with at least
906
        // one open bracket, so we should never get here.
907
        panic!("no open character class found")
908
    }
909

            
910
    /// Push the current set of class items on to the class parser's stack as
911
    /// the left hand side of the given operator.
912
    ///
913
    /// A fresh set union is returned, which should be used to build the right
914
    /// hand side of this operator.
915
    #[inline(never)]
916
    fn push_class_op(
917
        &self,
918
        next_kind: ast::ClassSetBinaryOpKind,
919
        next_union: ast::ClassSetUnion,
920
    ) -> ast::ClassSetUnion {
921
        let item = ast::ClassSet::Item(next_union.into_item());
922
        let new_lhs = self.pop_class_op(item);
923
        self.parser()
924
            .stack_class
925
            .borrow_mut()
926
            .push(ClassState::Op { kind: next_kind, lhs: new_lhs });
927
        ast::ClassSetUnion { span: self.span(), items: vec![] }
928
    }
929

            
930
    /// Pop a character class set from the character class parser stack. If the
931
    /// top of the stack is just an item (not an operation), then return the
932
    /// given set unchanged. If the top of the stack is an operation, then the
933
    /// given set will be used as the rhs of the operation on the top of the
934
    /// stack. In that case, the binary operation is returned as a set.
935
    #[inline(never)]
936
8
    fn pop_class_op(&self, rhs: ast::ClassSet) -> ast::ClassSet {
937
8
        let mut stack = self.parser().stack_class.borrow_mut();
938
8
        let (kind, lhs) = match stack.pop() {
939
            Some(ClassState::Op { kind, lhs }) => (kind, lhs),
940
8
            Some(state @ ClassState::Open { .. }) => {
941
8
                stack.push(state);
942
8
                return rhs;
943
            }
944
            None => unreachable!(),
945
        };
946
        let span = Span::new(lhs.span().start, rhs.span().end);
947
        ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
948
            span,
949
            kind,
950
            lhs: Box::new(lhs),
951
            rhs: Box::new(rhs),
952
        })
953
8
    }
954
}
955

            
956
impl<'s, P: Borrow<Parser>> ParserI<'s, P> {
957
    /// Parse the regular expression into an abstract syntax tree.
958
2
    fn parse(&self) -> Result<Ast> {
959
2
        self.parse_with_comments().map(|astc| astc.ast)
960
2
    }
961

            
962
    /// Parse the regular expression and return an abstract syntax tree with
963
    /// all of the comments found in the pattern.
964
2
    fn parse_with_comments(&self) -> Result<ast::WithComments> {
965
2
        assert_eq!(self.offset(), 0, "parser can only be used once");
966
2
        self.parser().reset();
967
2
        let mut concat = ast::Concat { span: self.span(), asts: vec![] };
968
        loop {
969
200
            self.bump_space();
970
200
            if self.is_eof() {
971
2
                break;
972
198
            }
973
198
            match self.char() {
974
18
                '(' => concat = self.push_group(concat)?,
975
16
                ')' => concat = self.pop_group(concat)?,
976
28
                '|' => concat = self.push_alternate(concat)?,
977
                '[' => {
978
8
                    let class = self.parse_set_class()?;
979
8
                    concat.asts.push(Ast::class_bracketed(class));
980
                }
981
                '?' => {
982
4
                    concat = self.parse_uncounted_repetition(
983
4
                        concat,
984
4
                        ast::RepetitionKind::ZeroOrOne,
985
4
                    )?;
986
                }
987
                '*' => {
988
2
                    concat = self.parse_uncounted_repetition(
989
2
                        concat,
990
2
                        ast::RepetitionKind::ZeroOrMore,
991
2
                    )?;
992
                }
993
                '+' => {
994
2
                    concat = self.parse_uncounted_repetition(
995
2
                        concat,
996
2
                        ast::RepetitionKind::OneOrMore,
997
2
                    )?;
998
                }
999
                '{' => {
2
                    concat = self.parse_counted_repetition(concat)?;
                }
118
                _ => concat.asts.push(self.parse_primitive()?.into_ast()),
            }
        }
2
        let ast = self.pop_group_end(concat)?;
2
        NestLimiter::new(self).check(&ast)?;
2
        Ok(ast::WithComments {
2
            ast,
2
            comments: mem::replace(
2
                &mut *self.parser().comments.borrow_mut(),
2
                vec![],
2
            ),
2
        })
2
    }
    /// Parses an uncounted repetition operation. An uncounted repetition
    /// operator includes ?, * and +, but does not include the {m,n} syntax.
    /// The given `kind` should correspond to the operator observed by the
    /// caller.
    ///
    /// This assumes that the parser is currently positioned at the repetition
    /// operator and advances the parser to the first character after the
    /// operator. (Note that the operator may include a single additional `?`,
    /// which makes the operator ungreedy.)
    ///
    /// The caller should include the concatenation that is being built. The
    /// concatenation returned includes the repetition operator applied to the
    /// last expression in the given concatenation.
    #[inline(never)]
8
    fn parse_uncounted_repetition(
8
        &self,
8
        mut concat: ast::Concat,
8
        kind: ast::RepetitionKind,
8
    ) -> Result<ast::Concat> {
8
        assert!(
8
            self.char() == '?' || self.char() == '*' || self.char() == '+'
        );
8
        let op_start = self.pos();
8
        let ast = match concat.asts.pop() {
8
            Some(ast) => ast,
            None => {
                return Err(
                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
                )
            }
        };
8
        match ast {
            Ast::Empty(_) | Ast::Flags(_) => {
                return Err(
                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
                )
            }
8
            _ => {}
8
        }
8
        let mut greedy = true;
8
        if self.bump() && self.char() == '?' {
            greedy = false;
            self.bump();
8
        }
8
        concat.asts.push(Ast::repetition(ast::Repetition {
8
            span: ast.span().with_end(self.pos()),
8
            op: ast::RepetitionOp {
8
                span: Span::new(op_start, self.pos()),
8
                kind,
8
            },
8
            greedy,
8
            ast: Box::new(ast),
8
        }));
8
        Ok(concat)
8
    }
    /// Parses a counted repetition operation. A counted repetition operator
    /// corresponds to the {m,n} syntax, and does not include the ?, * or +
    /// operators.
    ///
    /// This assumes that the parser is currently positioned at the opening `{`
    /// and advances the parser to the first character after the operator.
    /// (Note that the operator may include a single additional `?`, which
    /// makes the operator ungreedy.)
    ///
    /// The caller should include the concatenation that is being built. The
    /// concatenation returned includes the repetition operator applied to the
    /// last expression in the given concatenation.
    #[inline(never)]
2
    fn parse_counted_repetition(
2
        &self,
2
        mut concat: ast::Concat,
2
    ) -> Result<ast::Concat> {
2
        assert!(self.char() == '{');
2
        let start = self.pos();
2
        let ast = match concat.asts.pop() {
2
            Some(ast) => ast,
            None => {
                return Err(
                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
                )
            }
        };
2
        match ast {
            Ast::Empty(_) | Ast::Flags(_) => {
                return Err(
                    self.error(self.span(), ast::ErrorKind::RepetitionMissing)
                )
            }
2
            _ => {}
2
        }
2
        if !self.bump_and_bump_space() {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::RepetitionCountUnclosed,
            ));
2
        }
2
        let count_start = specialize_err(
2
            self.parse_decimal(),
2
            ast::ErrorKind::DecimalEmpty,
2
            ast::ErrorKind::RepetitionCountDecimalEmpty,
2
        )?;
2
        let mut range = ast::RepetitionRange::Exactly(count_start);
2
        if self.is_eof() {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::RepetitionCountUnclosed,
            ));
2
        }
2
        if self.char() == ',' {
2
            if !self.bump_and_bump_space() {
                return Err(self.error(
                    Span::new(start, self.pos()),
                    ast::ErrorKind::RepetitionCountUnclosed,
                ));
2
            }
2
            if self.char() != '}' {
2
                let count_end = specialize_err(
2
                    self.parse_decimal(),
2
                    ast::ErrorKind::DecimalEmpty,
2
                    ast::ErrorKind::RepetitionCountDecimalEmpty,
2
                )?;
2
                range = ast::RepetitionRange::Bounded(count_start, count_end);
            } else {
                range = ast::RepetitionRange::AtLeast(count_start);
            }
        }
2
        if self.is_eof() || self.char() != '}' {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::RepetitionCountUnclosed,
            ));
2
        }
2

            
2
        let mut greedy = true;
2
        if self.bump_and_bump_space() && self.char() == '?' {
            greedy = false;
            self.bump();
2
        }
2
        let op_span = Span::new(start, self.pos());
2
        if !range.is_valid() {
            return Err(
                self.error(op_span, ast::ErrorKind::RepetitionCountInvalid)
            );
2
        }
2
        concat.asts.push(Ast::repetition(ast::Repetition {
2
            span: ast.span().with_end(self.pos()),
2
            op: ast::RepetitionOp {
2
                span: op_span,
2
                kind: ast::RepetitionKind::Range(range),
2
            },
2
            greedy,
2
            ast: Box::new(ast),
2
        }));
2
        Ok(concat)
2
    }
    /// Parse a group (which contains a sub-expression) or a set of flags.
    ///
    /// If a group was found, then it is returned with an empty AST. If a set
    /// of flags is found, then that set is returned.
    ///
    /// The parser should be positioned at the opening parenthesis.
    ///
    /// This advances the parser to the character before the start of the
    /// sub-expression (in the case of a group) or to the closing parenthesis
    /// immediately following the set of flags.
    ///
    /// # Errors
    ///
    /// If flags are given and incorrectly specified, then a corresponding
    /// error is returned.
    ///
    /// If a capture name is given and it is incorrectly specified, then a
    /// corresponding error is returned.
    #[inline(never)]
18
    fn parse_group(&self) -> Result<Either<ast::SetFlags, ast::Group>> {
18
        assert_eq!(self.char(), '(');
18
        let open_span = self.span_char();
18
        self.bump();
18
        self.bump_space();
18
        if self.is_lookaround_prefix() {
            return Err(self.error(
                Span::new(open_span.start, self.span().end),
                ast::ErrorKind::UnsupportedLookAround,
            ));
18
        }
18
        let inner_span = self.span();
18
        let mut starts_with_p = true;
18
        if self.bump_if("?P<") || {
10
            starts_with_p = false;
10
            self.bump_if("?<")
        } {
8
            let capture_index = self.next_capture_index(open_span)?;
8
            let name = self.parse_capture_name(capture_index)?;
8
            Ok(Either::Right(ast::Group {
8
                span: open_span,
8
                kind: ast::GroupKind::CaptureName { starts_with_p, name },
8
                ast: Box::new(Ast::empty(self.span())),
8
            }))
10
        } else if self.bump_if("?") {
10
            if self.is_eof() {
                return Err(
                    self.error(open_span, ast::ErrorKind::GroupUnclosed)
                );
10
            }
10
            let flags = self.parse_flags()?;
10
            let char_end = self.char();
10
            self.bump();
10
            if char_end == ')' {
                // We don't allow empty flags, e.g., `(?)`. We instead
                // interpret it as a repetition operator missing its argument.
2
                if flags.items.is_empty() {
                    return Err(self.error(
                        inner_span,
                        ast::ErrorKind::RepetitionMissing,
                    ));
2
                }
2
                Ok(Either::Left(ast::SetFlags {
2
                    span: Span { end: self.pos(), ..open_span },
2
                    flags,
2
                }))
            } else {
8
                assert_eq!(char_end, ':');
8
                Ok(Either::Right(ast::Group {
8
                    span: open_span,
8
                    kind: ast::GroupKind::NonCapturing(flags),
8
                    ast: Box::new(Ast::empty(self.span())),
8
                }))
            }
        } else {
            let capture_index = self.next_capture_index(open_span)?;
            Ok(Either::Right(ast::Group {
                span: open_span,
                kind: ast::GroupKind::CaptureIndex(capture_index),
                ast: Box::new(Ast::empty(self.span())),
            }))
        }
18
    }
    /// Parses a capture group name. Assumes that the parser is positioned at
    /// the first character in the name following the opening `<` (and may
    /// possibly be EOF). This advances the parser to the first character
    /// following the closing `>`.
    ///
    /// The caller must provide the capture index of the group for this name.
    #[inline(never)]
8
    fn parse_capture_name(
8
        &self,
8
        capture_index: u32,
8
    ) -> Result<ast::CaptureName> {
8
        if self.is_eof() {
            return Err(self
                .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
8
        }
8
        let start = self.pos();
        loop {
62
            if self.char() == '>' {
8
                break;
54
            }
54
            if !is_capture_char(self.char(), self.pos() == start) {
                return Err(self.error(
                    self.span_char(),
                    ast::ErrorKind::GroupNameInvalid,
                ));
54
            }
54
            if !self.bump() {
                break;
54
            }
        }
8
        let end = self.pos();
8
        if self.is_eof() {
            return Err(self
                .error(self.span(), ast::ErrorKind::GroupNameUnexpectedEof));
8
        }
8
        assert_eq!(self.char(), '>');
8
        self.bump();
8
        let name = &self.pattern()[start.offset..end.offset];
8
        if name.is_empty() {
            return Err(self.error(
                Span::new(start, start),
                ast::ErrorKind::GroupNameEmpty,
            ));
8
        }
8
        let capname = ast::CaptureName {
8
            span: Span::new(start, end),
8
            name: name.to_string(),
8
            index: capture_index,
8
        };
8
        self.add_capture_name(&capname)?;
8
        Ok(capname)
8
    }
    /// Parse a sequence of flags starting at the current character.
    ///
    /// This advances the parser to the character immediately following the
    /// flags, which is guaranteed to be either `:` or `)`.
    ///
    /// # Errors
    ///
    /// If any flags are duplicated, then an error is returned.
    ///
    /// If the negation operator is used more than once, then an error is
    /// returned.
    ///
    /// If no flags could be found or if the negation operation is not followed
    /// by any flags, then an error is returned.
    #[inline(never)]
10
    fn parse_flags(&self) -> Result<ast::Flags> {
10
        let mut flags = ast::Flags { span: self.span(), items: vec![] };
10
        let mut last_was_negation = None;
16
        while self.char() != ':' && self.char() != ')' {
6
            if self.char() == '-' {
                last_was_negation = Some(self.span_char());
                let item = ast::FlagsItem {
                    span: self.span_char(),
                    kind: ast::FlagsItemKind::Negation,
                };
                if let Some(i) = flags.add_item(item) {
                    return Err(self.error(
                        self.span_char(),
                        ast::ErrorKind::FlagRepeatedNegation {
                            original: flags.items[i].span,
                        },
                    ));
                }
            } else {
6
                last_was_negation = None;
6
                let item = ast::FlagsItem {
6
                    span: self.span_char(),
6
                    kind: ast::FlagsItemKind::Flag(self.parse_flag()?),
                };
6
                if let Some(i) = flags.add_item(item) {
                    return Err(self.error(
                        self.span_char(),
                        ast::ErrorKind::FlagDuplicate {
                            original: flags.items[i].span,
                        },
                    ));
6
                }
            }
6
            if !self.bump() {
                return Err(
                    self.error(self.span(), ast::ErrorKind::FlagUnexpectedEof)
                );
6
            }
        }
10
        if let Some(span) = last_was_negation {
            return Err(self.error(span, ast::ErrorKind::FlagDanglingNegation));
10
        }
10
        flags.span.end = self.pos();
10
        Ok(flags)
10
    }
    /// Parse the current character as a flag. Do not advance the parser.
    ///
    /// # Errors
    ///
    /// If the flag is not recognized, then an error is returned.
    #[inline(never)]
6
    fn parse_flag(&self) -> Result<ast::Flag> {
6
        match self.char() {
4
            'i' => Ok(ast::Flag::CaseInsensitive),
            'm' => Ok(ast::Flag::MultiLine),
            's' => Ok(ast::Flag::DotMatchesNewLine),
            'U' => Ok(ast::Flag::SwapGreed),
            'u' => Ok(ast::Flag::Unicode),
            'R' => Ok(ast::Flag::CRLF),
2
            'x' => Ok(ast::Flag::IgnoreWhitespace),
            _ => {
                Err(self
                    .error(self.span_char(), ast::ErrorKind::FlagUnrecognized))
            }
        }
6
    }
    /// Parse a primitive AST. e.g., A literal, non-set character class or
    /// assertion.
    ///
    /// This assumes that the parser expects a primitive at the current
    /// location. i.e., All other non-primitive cases have been handled.
    /// For example, if the parser's position is at `|`, then `|` will be
    /// treated as a literal (e.g., inside a character class).
    ///
    /// This advances the parser to the first character immediately following
    /// the primitive.
118
    fn parse_primitive(&self) -> Result<Primitive> {
118
        match self.char() {
4
            '\\' => self.parse_escape(),
            '.' => {
                let ast = Primitive::Dot(self.span_char());
                self.bump();
                Ok(ast)
            }
            '^' => {
4
                let ast = Primitive::Assertion(ast::Assertion {
4
                    span: self.span_char(),
4
                    kind: ast::AssertionKind::StartLine,
4
                });
4
                self.bump();
4
                Ok(ast)
            }
            '$' => {
4
                let ast = Primitive::Assertion(ast::Assertion {
4
                    span: self.span_char(),
4
                    kind: ast::AssertionKind::EndLine,
4
                });
4
                self.bump();
4
                Ok(ast)
            }
106
            c => {
106
                let ast = Primitive::Literal(ast::Literal {
106
                    span: self.span_char(),
106
                    kind: ast::LiteralKind::Verbatim,
106
                    c,
106
                });
106
                self.bump();
106
                Ok(ast)
            }
        }
118
    }
    /// Parse an escape sequence as a primitive AST.
    ///
    /// This assumes the parser is positioned at the start of the escape
    /// sequence, i.e., `\`. It advances the parser to the first position
    /// immediately following the escape sequence.
    #[inline(never)]
8
    fn parse_escape(&self) -> Result<Primitive> {
8
        assert_eq!(self.char(), '\\');
8
        let start = self.pos();
8
        if !self.bump() {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::EscapeUnexpectedEof,
            ));
8
        }
8
        let c = self.char();
        // Put some of the more complicated routines into helpers.
        match c {
8
            '0'..='7' => {
                if !self.parser().octal {
                    return Err(self.error(
                        Span::new(start, self.span_char().end),
                        ast::ErrorKind::UnsupportedBackreference,
                    ));
                }
                let mut lit = self.parse_octal();
                lit.span.start = start;
                return Ok(Primitive::Literal(lit));
            }
8
            '8'..='9' if !self.parser().octal => {
                return Err(self.error(
                    Span::new(start, self.span_char().end),
                    ast::ErrorKind::UnsupportedBackreference,
                ));
            }
            'x' | 'u' | 'U' => {
                let mut lit = self.parse_hex()?;
                lit.span.start = start;
                return Ok(Primitive::Literal(lit));
            }
            'p' | 'P' => {
                let mut cls = self.parse_unicode_class()?;
                cls.span.start = start;
                return Ok(Primitive::Unicode(cls));
            }
            'd' | 's' | 'w' | 'D' | 'S' | 'W' => {
2
                let mut cls = self.parse_perl_class();
2
                cls.span.start = start;
2
                return Ok(Primitive::Perl(cls));
            }
6
            _ => {}
6
        }
6

            
6
        // Handle all of the one letter sequences inline.
6
        self.bump();
6
        let span = Span::new(start, self.pos());
6
        if is_meta_character(c) {
6
            return Ok(Primitive::Literal(ast::Literal {
6
                span,
6
                kind: ast::LiteralKind::Meta,
6
                c,
6
            }));
        }
        if is_escapeable_character(c) {
            return Ok(Primitive::Literal(ast::Literal {
                span,
                kind: ast::LiteralKind::Superfluous,
                c,
            }));
        }
        let special = |kind, c| {
            Ok(Primitive::Literal(ast::Literal {
                span,
                kind: ast::LiteralKind::Special(kind),
                c,
            }))
        };
        match c {
            'a' => special(ast::SpecialLiteralKind::Bell, '\x07'),
            'f' => special(ast::SpecialLiteralKind::FormFeed, '\x0C'),
            't' => special(ast::SpecialLiteralKind::Tab, '\t'),
            'n' => special(ast::SpecialLiteralKind::LineFeed, '\n'),
            'r' => special(ast::SpecialLiteralKind::CarriageReturn, '\r'),
            'v' => special(ast::SpecialLiteralKind::VerticalTab, '\x0B'),
            'A' => Ok(Primitive::Assertion(ast::Assertion {
                span,
                kind: ast::AssertionKind::StartText,
            })),
            'z' => Ok(Primitive::Assertion(ast::Assertion {
                span,
                kind: ast::AssertionKind::EndText,
            })),
            'b' => {
                let mut wb = ast::Assertion {
                    span,
                    kind: ast::AssertionKind::WordBoundary,
                };
                // After a \b, we "try" to parse things like \b{start} for
                // special word boundary assertions.
                if !self.is_eof() && self.char() == '{' {
                    if let Some(kind) =
                        self.maybe_parse_special_word_boundary(start)?
                    {
                        wb.kind = kind;
                        wb.span.end = self.pos();
                    }
                }
                Ok(Primitive::Assertion(wb))
            }
            'B' => Ok(Primitive::Assertion(ast::Assertion {
                span,
                kind: ast::AssertionKind::NotWordBoundary,
            })),
            '<' => Ok(Primitive::Assertion(ast::Assertion {
                span,
                kind: ast::AssertionKind::WordBoundaryStartAngle,
            })),
            '>' => Ok(Primitive::Assertion(ast::Assertion {
                span,
                kind: ast::AssertionKind::WordBoundaryEndAngle,
            })),
            _ => Err(self.error(span, ast::ErrorKind::EscapeUnrecognized)),
        }
8
    }
    /// Attempt to parse a specialty word boundary. That is, `\b{start}`,
    /// `\b{end}`, `\b{start-half}` or `\b{end-half}`.
    ///
    /// This is similar to `maybe_parse_ascii_class` in that, in most cases,
    /// if it fails it will just return `None` with no error. This is done
    /// because `\b{5}` is a valid expression and we want to let that be parsed
    /// by the existing counted repetition parsing code. (I thought about just
    /// invoking the counted repetition code from here, but it seemed a little
    /// ham-fisted.)
    ///
    /// Unlike `maybe_parse_ascii_class` though, this can return an error.
    /// Namely, if we definitely know it isn't a counted repetition, then we
    /// return an error specific to the specialty word boundaries.
    ///
    /// This assumes the parser is positioned at a `{` immediately following
    /// a `\b`. When `None` is returned, the parser is returned to the position
    /// at which it started: pointing at a `{`.
    ///
    /// The position given should correspond to the start of the `\b`.
    fn maybe_parse_special_word_boundary(
        &self,
        wb_start: Position,
    ) -> Result<Option<ast::AssertionKind>> {
        assert_eq!(self.char(), '{');
        let is_valid_char = |c| match c {
            'A'..='Z' | 'a'..='z' | '-' => true,
            _ => false,
        };
        let start = self.pos();
        if !self.bump_and_bump_space() {
            return Err(self.error(
                Span::new(wb_start, self.pos()),
                ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
            ));
        }
        let start_contents = self.pos();
        // This is one of the critical bits: if the first non-whitespace
        // character isn't in [-A-Za-z] (i.e., this can't be a special word
        // boundary), then we bail and let the counted repetition parser deal
        // with this.
        if !is_valid_char(self.char()) {
            self.parser().pos.set(start);
            return Ok(None);
        }
        // Now collect up our chars until we see a '}'.
        let mut scratch = self.parser().scratch.borrow_mut();
        scratch.clear();
        while !self.is_eof() && is_valid_char(self.char()) {
            scratch.push(self.char());
            self.bump_and_bump_space();
        }
        if self.is_eof() || self.char() != '}' {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::SpecialWordBoundaryUnclosed,
            ));
        }
        let end = self.pos();
        self.bump();
        let kind = match scratch.as_str() {
            "start" => ast::AssertionKind::WordBoundaryStart,
            "end" => ast::AssertionKind::WordBoundaryEnd,
            "start-half" => ast::AssertionKind::WordBoundaryStartHalf,
            "end-half" => ast::AssertionKind::WordBoundaryEndHalf,
            _ => {
                return Err(self.error(
                    Span::new(start_contents, end),
                    ast::ErrorKind::SpecialWordBoundaryUnrecognized,
                ))
            }
        };
        Ok(Some(kind))
    }
    /// Parse an octal representation of a Unicode codepoint up to 3 digits
    /// long. This expects the parser to be positioned at the first octal
    /// digit and advances the parser to the first character immediately
    /// following the octal number. This also assumes that parsing octal
    /// escapes is enabled.
    ///
    /// Assuming the preconditions are met, this routine can never fail.
    #[inline(never)]
    fn parse_octal(&self) -> ast::Literal {
        assert!(self.parser().octal);
        assert!('0' <= self.char() && self.char() <= '7');
        let start = self.pos();
        // Parse up to two more digits.
        while self.bump()
            && '0' <= self.char()
            && self.char() <= '7'
            && self.pos().offset - start.offset <= 2
        {}
        let end = self.pos();
        let octal = &self.pattern()[start.offset..end.offset];
        // Parsing the octal should never fail since the above guarantees a
        // valid number.
        let codepoint =
            u32::from_str_radix(octal, 8).expect("valid octal number");
        // The max value for 3 digit octal is 0777 = 511 and [0, 511] has no
        // invalid Unicode scalar values.
        let c = char::from_u32(codepoint).expect("Unicode scalar value");
        ast::Literal {
            span: Span::new(start, end),
            kind: ast::LiteralKind::Octal,
            c,
        }
    }
    /// Parse a hex representation of a Unicode codepoint. This handles both
    /// hex notations, i.e., `\xFF` and `\x{FFFF}`. This expects the parser to
    /// be positioned at the `x`, `u` or `U` prefix. The parser is advanced to
    /// the first character immediately following the hexadecimal literal.
    #[inline(never)]
    fn parse_hex(&self) -> Result<ast::Literal> {
        assert!(
            self.char() == 'x' || self.char() == 'u' || self.char() == 'U'
        );
        let hex_kind = match self.char() {
            'x' => ast::HexLiteralKind::X,
            'u' => ast::HexLiteralKind::UnicodeShort,
            _ => ast::HexLiteralKind::UnicodeLong,
        };
        if !self.bump_and_bump_space() {
            return Err(
                self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
            );
        }
        if self.char() == '{' {
            self.parse_hex_brace(hex_kind)
        } else {
            self.parse_hex_digits(hex_kind)
        }
    }
    /// Parse an N-digit hex representation of a Unicode codepoint. This
    /// expects the parser to be positioned at the first digit and will advance
    /// the parser to the first character immediately following the escape
    /// sequence.
    ///
    /// The number of digits given must be 2 (for `\xNN`), 4 (for `\uNNNN`)
    /// or 8 (for `\UNNNNNNNN`).
    #[inline(never)]
    fn parse_hex_digits(
        &self,
        kind: ast::HexLiteralKind,
    ) -> Result<ast::Literal> {
        let mut scratch = self.parser().scratch.borrow_mut();
        scratch.clear();
        let start = self.pos();
        for i in 0..kind.digits() {
            if i > 0 && !self.bump_and_bump_space() {
                return Err(self
                    .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
            }
            if !is_hex(self.char()) {
                return Err(self.error(
                    self.span_char(),
                    ast::ErrorKind::EscapeHexInvalidDigit,
                ));
            }
            scratch.push(self.char());
        }
        // The final bump just moves the parser past the literal, which may
        // be EOF.
        self.bump_and_bump_space();
        let end = self.pos();
        let hex = scratch.as_str();
        match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
            None => Err(self.error(
                Span::new(start, end),
                ast::ErrorKind::EscapeHexInvalid,
            )),
            Some(c) => Ok(ast::Literal {
                span: Span::new(start, end),
                kind: ast::LiteralKind::HexFixed(kind),
                c,
            }),
        }
    }
    /// Parse a hex representation of any Unicode scalar value. This expects
    /// the parser to be positioned at the opening brace `{` and will advance
    /// the parser to the first character following the closing brace `}`.
    #[inline(never)]
    fn parse_hex_brace(
        &self,
        kind: ast::HexLiteralKind,
    ) -> Result<ast::Literal> {
        let mut scratch = self.parser().scratch.borrow_mut();
        scratch.clear();
        let brace_pos = self.pos();
        let start = self.span_char().end;
        while self.bump_and_bump_space() && self.char() != '}' {
            if !is_hex(self.char()) {
                return Err(self.error(
                    self.span_char(),
                    ast::ErrorKind::EscapeHexInvalidDigit,
                ));
            }
            scratch.push(self.char());
        }
        if self.is_eof() {
            return Err(self.error(
                Span::new(brace_pos, self.pos()),
                ast::ErrorKind::EscapeUnexpectedEof,
            ));
        }
        let end = self.pos();
        let hex = scratch.as_str();
        assert_eq!(self.char(), '}');
        self.bump_and_bump_space();
        if hex.is_empty() {
            return Err(self.error(
                Span::new(brace_pos, self.pos()),
                ast::ErrorKind::EscapeHexEmpty,
            ));
        }
        match u32::from_str_radix(hex, 16).ok().and_then(char::from_u32) {
            None => Err(self.error(
                Span::new(start, end),
                ast::ErrorKind::EscapeHexInvalid,
            )),
            Some(c) => Ok(ast::Literal {
                span: Span::new(start, self.pos()),
                kind: ast::LiteralKind::HexBrace(kind),
                c,
            }),
        }
    }
    /// Parse a decimal number into a u32 while trimming leading and trailing
    /// whitespace.
    ///
    /// This expects the parser to be positioned at the first position where
    /// a decimal digit could occur. This will advance the parser to the byte
    /// immediately following the last contiguous decimal digit.
    ///
    /// If no decimal digit could be found or if there was a problem parsing
    /// the complete set of digits into a u32, then an error is returned.
4
    fn parse_decimal(&self) -> Result<u32> {
4
        let mut scratch = self.parser().scratch.borrow_mut();
4
        scratch.clear();
4
        while !self.is_eof() && self.char().is_whitespace() {
            self.bump();
        }
4
        let start = self.pos();
8
        while !self.is_eof() && '0' <= self.char() && self.char() <= '9' {
4
            scratch.push(self.char());
4
            self.bump_and_bump_space();
4
        }
4
        let span = Span::new(start, self.pos());
4
        while !self.is_eof() && self.char().is_whitespace() {
            self.bump_and_bump_space();
        }
4
        let digits = scratch.as_str();
4
        if digits.is_empty() {
            return Err(self.error(span, ast::ErrorKind::DecimalEmpty));
4
        }
4
        match u32::from_str_radix(digits, 10).ok() {
4
            Some(n) => Ok(n),
            None => Err(self.error(span, ast::ErrorKind::DecimalInvalid)),
        }
4
    }
    /// Parse a standard character class consisting primarily of characters or
    /// character ranges, but can also contain nested character classes of
    /// any type (sans `.`).
    ///
    /// This assumes the parser is positioned at the opening `[`. If parsing
    /// is successful, then the parser is advanced to the position immediately
    /// following the closing `]`.
    #[inline(never)]
8
    fn parse_set_class(&self) -> Result<ast::ClassBracketed> {
8
        assert_eq!(self.char(), '[');
8
        let mut union =
8
            ast::ClassSetUnion { span: self.span(), items: vec![] };
        loop {
28
            self.bump_space();
28
            if self.is_eof() {
                return Err(self.unclosed_class_error());
28
            }
28
            match self.char() {
                '[' => {
                    // If we've already parsed the opening bracket, then
                    // attempt to treat this as the beginning of an ASCII
                    // class. If ASCII class parsing fails, then the parser
                    // backs up to `[`.
8
                    if !self.parser().stack_class.borrow().is_empty() {
                        if let Some(cls) = self.maybe_parse_ascii_class() {
                            union.push(ast::ClassSetItem::Ascii(cls));
                            continue;
                        }
8
                    }
8
                    union = self.push_class_open(union)?;
                }
8
                ']' => match self.pop_class(union)? {
                    Either::Left(nested_union) => {
                        union = nested_union;
                    }
8
                    Either::Right(class) => return Ok(class),
                },
                '&' if self.peek() == Some('&') => {
                    assert!(self.bump_if("&&"));
                    union = self.push_class_op(
                        ast::ClassSetBinaryOpKind::Intersection,
                        union,
                    );
                }
2
                '-' if self.peek() == Some('-') => {
                    assert!(self.bump_if("--"));
                    union = self.push_class_op(
                        ast::ClassSetBinaryOpKind::Difference,
                        union,
                    );
                }
                '~' if self.peek() == Some('~') => {
                    assert!(self.bump_if("~~"));
                    union = self.push_class_op(
                        ast::ClassSetBinaryOpKind::SymmetricDifference,
                        union,
                    );
                }
                _ => {
12
                    union.push(self.parse_set_class_range()?);
                }
            }
        }
8
    }
    /// Parse a single primitive item in a character class set. The item to
    /// be parsed can either be one of a simple literal character, a range
    /// between two simple literal characters or a "primitive" character
    /// class like \w or \p{Greek}.
    ///
    /// If an invalid escape is found, or if a character class is found where
    /// a simple literal is expected (e.g., in a range), then an error is
    /// returned.
    #[inline(never)]
12
    fn parse_set_class_range(&self) -> Result<ast::ClassSetItem> {
12
        let prim1 = self.parse_set_class_item()?;
12
        self.bump_space();
12
        if self.is_eof() {
            return Err(self.unclosed_class_error());
12
        }
12
        // If the next char isn't a `-`, then we don't have a range.
12
        // There are two exceptions. If the char after a `-` is a `]`, then
12
        // `-` is interpreted as a literal `-`. Alternatively, if the char
12
        // after a `-` is a `-`, then `--` corresponds to a "difference"
12
        // operation.
12
        if self.char() != '-'
6
            || self.peek_space() == Some(']')
4
            || self.peek_space() == Some('-')
        {
8
            return prim1.into_class_set_item(self);
4
        }
4
        // OK, now we're parsing a range, so bump past the `-` and parse the
4
        // second half of the range.
4
        if !self.bump_and_bump_space() {
            return Err(self.unclosed_class_error());
4
        }
4
        let prim2 = self.parse_set_class_item()?;
4
        let range = ast::ClassSetRange {
4
            span: Span::new(prim1.span().start, prim2.span().end),
4
            start: prim1.into_class_literal(self)?,
4
            end: prim2.into_class_literal(self)?,
        };
4
        if !range.is_valid() {
            return Err(
                self.error(range.span, ast::ErrorKind::ClassRangeInvalid)
            );
4
        }
4
        Ok(ast::ClassSetItem::Range(range))
12
    }
    /// Parse a single item in a character class as a primitive, where the
    /// primitive either consists of a verbatim literal or a single escape
    /// sequence.
    ///
    /// This assumes the parser is positioned at the beginning of a primitive,
    /// and advances the parser to the first position after the primitive if
    /// successful.
    ///
    /// Note that it is the caller's responsibility to report an error if an
    /// illegal primitive was parsed.
    #[inline(never)]
16
    fn parse_set_class_item(&self) -> Result<Primitive> {
16
        if self.char() == '\\' {
4
            self.parse_escape()
        } else {
12
            let x = Primitive::Literal(ast::Literal {
12
                span: self.span_char(),
12
                kind: ast::LiteralKind::Verbatim,
12
                c: self.char(),
12
            });
12
            self.bump();
12
            Ok(x)
        }
16
    }
    /// Parses the opening of a character class set. This includes the opening
    /// bracket along with `^` if present to indicate negation. This also
    /// starts parsing the opening set of unioned items if applicable, since
    /// there are special rules applied to certain characters in the opening
    /// of a character class. For example, `[^]]` is the class of all
    /// characters not equal to `]`. (`]` would need to be escaped in any other
    /// position.) Similarly for `-`.
    ///
    /// In all cases, the op inside the returned `ast::ClassBracketed` is an
    /// empty union. This empty union should be replaced with the actual item
    /// when it is popped from the parser's stack.
    ///
    /// This assumes the parser is positioned at the opening `[` and advances
    /// the parser to the first non-special byte of the character class.
    ///
    /// An error is returned if EOF is found.
    #[inline(never)]
8
    fn parse_set_class_open(
8
        &self,
8
    ) -> Result<(ast::ClassBracketed, ast::ClassSetUnion)> {
8
        assert_eq!(self.char(), '[');
8
        let start = self.pos();
8
        if !self.bump_and_bump_space() {
            return Err(self.error(
                Span::new(start, self.pos()),
                ast::ErrorKind::ClassUnclosed,
            ));
8
        }
8
        let negated = if self.char() != '^' {
6
            false
        } else {
2
            if !self.bump_and_bump_space() {
                return Err(self.error(
                    Span::new(start, self.pos()),
                    ast::ErrorKind::ClassUnclosed,
                ));
2
            }
2
            true
        };
        // Accept any number of `-` as literal `-`.
8
        let mut union =
8
            ast::ClassSetUnion { span: self.span(), items: vec![] };
8
        while self.char() == '-' {
            union.push(ast::ClassSetItem::Literal(ast::Literal {
                span: self.span_char(),
                kind: ast::LiteralKind::Verbatim,
                c: '-',
            }));
            if !self.bump_and_bump_space() {
                return Err(self.error(
                    Span::new(start, start),
                    ast::ErrorKind::ClassUnclosed,
                ));
            }
        }
        // If `]` is the *first* char in a set, then interpret it as a literal
        // `]`. That is, an empty class is impossible to write.
8
        if union.items.is_empty() && self.char() == ']' {
            union.push(ast::ClassSetItem::Literal(ast::Literal {
                span: self.span_char(),
                kind: ast::LiteralKind::Verbatim,
                c: ']',
            }));
            if !self.bump_and_bump_space() {
                return Err(self.error(
                    Span::new(start, self.pos()),
                    ast::ErrorKind::ClassUnclosed,
                ));
            }
8
        }
8
        let set = ast::ClassBracketed {
8
            span: Span::new(start, self.pos()),
8
            negated,
8
            kind: ast::ClassSet::union(ast::ClassSetUnion {
8
                span: Span::new(union.span.start, union.span.start),
8
                items: vec![],
8
            }),
8
        };
8
        Ok((set, union))
8
    }
    /// Attempt to parse an ASCII character class, e.g., `[:alnum:]`.
    ///
    /// This assumes the parser is positioned at the opening `[`.
    ///
    /// If no valid ASCII character class could be found, then this does not
    /// advance the parser and `None` is returned. Otherwise, the parser is
    /// advanced to the first byte following the closing `]` and the
    /// corresponding ASCII class is returned.
    #[inline(never)]
    fn maybe_parse_ascii_class(&self) -> Option<ast::ClassAscii> {
        // ASCII character classes are interesting from a parsing perspective
        // because parsing cannot fail with any interesting error. For example,
        // in order to use an ASCII character class, it must be enclosed in
        // double brackets, e.g., `[[:alnum:]]`. Alternatively, you might think
        // of it as "ASCII character classes have the syntax `[:NAME:]` which
        // can only appear within character brackets." This means that things
        // like `[[:lower:]A]` are legal constructs.
        //
        // However, if one types an incorrect ASCII character class, e.g.,
        // `[[:loower:]]`, then we treat that as a normal nested character
        // class containing the characters `:elorw`. One might argue that we
        // should return an error instead since the repeated colons give away
        // the intent to write an ASCII class. But what if the user typed
        // `[[:lower]]` instead? How can we tell that was intended to be an
        // ASCII class and not just a normal nested class?
        //
        // Reasonable people can probably disagree over this, but for better
        // or worse, we implement semantics that never fails at the expense
        // of better failure modes.
        assert_eq!(self.char(), '[');
        // If parsing fails, then we back up the parser to this starting point.
        let start = self.pos();
        let mut negated = false;
        if !self.bump() || self.char() != ':' {
            self.parser().pos.set(start);
            return None;
        }
        if !self.bump() {
            self.parser().pos.set(start);
            return None;
        }
        if self.char() == '^' {
            negated = true;
            if !self.bump() {
                self.parser().pos.set(start);
                return None;
            }
        }
        let name_start = self.offset();
        while self.char() != ':' && self.bump() {}
        if self.is_eof() {
            self.parser().pos.set(start);
            return None;
        }
        let name = &self.pattern()[name_start..self.offset()];
        if !self.bump_if(":]") {
            self.parser().pos.set(start);
            return None;
        }
        let kind = match ast::ClassAsciiKind::from_name(name) {
            Some(kind) => kind,
            None => {
                self.parser().pos.set(start);
                return None;
            }
        };
        Some(ast::ClassAscii {
            span: Span::new(start, self.pos()),
            kind,
            negated,
        })
    }
    /// Parse a Unicode class in either the single character notation, `\pN`
    /// or the multi-character bracketed notation, `\p{Greek}`. This assumes
    /// the parser is positioned at the `p` (or `P` for negation) and will
    /// advance the parser to the character immediately following the class.
    ///
    /// Note that this does not check whether the class name is valid or not.
    #[inline(never)]
    fn parse_unicode_class(&self) -> Result<ast::ClassUnicode> {
        assert!(self.char() == 'p' || self.char() == 'P');
        let mut scratch = self.parser().scratch.borrow_mut();
        scratch.clear();
        let negated = self.char() == 'P';
        if !self.bump_and_bump_space() {
            return Err(
                self.error(self.span(), ast::ErrorKind::EscapeUnexpectedEof)
            );
        }
        let (start, kind) = if self.char() == '{' {
            let start = self.span_char().end;
            while self.bump_and_bump_space() && self.char() != '}' {
                scratch.push(self.char());
            }
            if self.is_eof() {
                return Err(self
                    .error(self.span(), ast::ErrorKind::EscapeUnexpectedEof));
            }
            assert_eq!(self.char(), '}');
            self.bump();
            let name = scratch.as_str();
            if let Some(i) = name.find("!=") {
                (
                    start,
                    ast::ClassUnicodeKind::NamedValue {
                        op: ast::ClassUnicodeOpKind::NotEqual,
                        name: name[..i].to_string(),
                        value: name[i + 2..].to_string(),
                    },
                )
            } else if let Some(i) = name.find(':') {
                (
                    start,
                    ast::ClassUnicodeKind::NamedValue {
                        op: ast::ClassUnicodeOpKind::Colon,
                        name: name[..i].to_string(),
                        value: name[i + 1..].to_string(),
                    },
                )
            } else if let Some(i) = name.find('=') {
                (
                    start,
                    ast::ClassUnicodeKind::NamedValue {
                        op: ast::ClassUnicodeOpKind::Equal,
                        name: name[..i].to_string(),
                        value: name[i + 1..].to_string(),
                    },
                )
            } else {
                (start, ast::ClassUnicodeKind::Named(name.to_string()))
            }
        } else {
            let start = self.pos();
            let c = self.char();
            if c == '\\' {
                return Err(self.error(
                    self.span_char(),
                    ast::ErrorKind::UnicodeClassInvalid,
                ));
            }
            self.bump_and_bump_space();
            let kind = ast::ClassUnicodeKind::OneLetter(c);
            (start, kind)
        };
        Ok(ast::ClassUnicode {
            span: Span::new(start, self.pos()),
            negated,
            kind,
        })
    }
    /// Parse a Perl character class, e.g., `\d` or `\W`. This assumes the
    /// parser is currently at a valid character class name and will be
    /// advanced to the character immediately following the class.
    #[inline(never)]
2
    fn parse_perl_class(&self) -> ast::ClassPerl {
2
        let c = self.char();
2
        let span = self.span_char();
2
        self.bump();
2
        let (negated, kind) = match c {
            'd' => (false, ast::ClassPerlKind::Digit),
            'D' => (true, ast::ClassPerlKind::Digit),
            's' => (false, ast::ClassPerlKind::Space),
            'S' => (true, ast::ClassPerlKind::Space),
2
            'w' => (false, ast::ClassPerlKind::Word),
            'W' => (true, ast::ClassPerlKind::Word),
            c => panic!("expected valid Perl class but got '{}'", c),
        };
2
        ast::ClassPerl { span, kind, negated }
2
    }
}
/// A type that traverses a fully parsed Ast and checks whether its depth
/// exceeds the specified nesting limit. If it does, then an error is returned.
#[derive(Debug)]
struct NestLimiter<'p, 's, P> {
    /// The parser that is checking the nest limit.
    p: &'p ParserI<'s, P>,
    /// The current depth while walking an Ast.
    depth: u32,
}
impl<'p, 's, P: Borrow<Parser>> NestLimiter<'p, 's, P> {
2
    fn new(p: &'p ParserI<'s, P>) -> NestLimiter<'p, 's, P> {
2
        NestLimiter { p, depth: 0 }
2
    }
    #[inline(never)]
2
    fn check(self, ast: &Ast) -> Result<()> {
2
        ast::visit(ast, self)
2
    }
76
    fn increment_depth(&mut self, span: &Span) -> Result<()> {
76
        let new = self.depth.checked_add(1).ok_or_else(|| {
            self.p.error(
                span.clone(),
                ast::ErrorKind::NestLimitExceeded(u32::MAX),
            )
76
        })?;
76
        let limit = self.p.parser().nest_limit;
76
        if new > limit {
            return Err(self.p.error(
                span.clone(),
                ast::ErrorKind::NestLimitExceeded(limit),
            ));
76
        }
76
        self.depth = new;
76
        Ok(())
76
    }
76
    fn decrement_depth(&mut self) {
76
        // Assuming the correctness of the visitor, this should never drop
76
        // below 0.
76
        self.depth = self.depth.checked_sub(1).unwrap();
76
    }
}
impl<'p, 's, P: Borrow<Parser>> ast::Visitor for NestLimiter<'p, 's, P> {
    type Output = ();
    type Err = ast::Error;
2
    fn finish(self) -> Result<()> {
2
        Ok(())
2
    }
194
    fn visit_pre(&mut self, ast: &Ast) -> Result<()> {
194
        let span = match *ast {
            Ast::Empty(_)
            | Ast::Flags(_)
            | Ast::Literal(_)
            | Ast::Dot(_)
            | Ast::Assertion(_)
            | Ast::ClassUnicode(_)
            | Ast::ClassPerl(_) => {
                // These are all base cases, so we don't increment depth.
120
                return Ok(());
            }
8
            Ast::ClassBracketed(ref x) => &x.span,
10
            Ast::Repetition(ref x) => &x.span,
16
            Ast::Group(ref x) => &x.span,
8
            Ast::Alternation(ref x) => &x.span,
32
            Ast::Concat(ref x) => &x.span,
        };
74
        self.increment_depth(span)
194
    }
194
    fn visit_post(&mut self, ast: &Ast) -> Result<()> {
194
        match *ast {
            Ast::Empty(_)
            | Ast::Flags(_)
            | Ast::Literal(_)
            | Ast::Dot(_)
            | Ast::Assertion(_)
            | Ast::ClassUnicode(_)
            | Ast::ClassPerl(_) => {
                // These are all base cases, so we don't decrement depth.
120
                Ok(())
            }
            Ast::ClassBracketed(_)
            | Ast::Repetition(_)
            | Ast::Group(_)
            | Ast::Alternation(_)
            | Ast::Concat(_) => {
74
                self.decrement_depth();
74
                Ok(())
            }
        }
194
    }
14
    fn visit_class_set_item_pre(
14
        &mut self,
14
        ast: &ast::ClassSetItem,
14
    ) -> Result<()> {
14
        let span = match *ast {
            ast::ClassSetItem::Empty(_)
            | ast::ClassSetItem::Literal(_)
            | ast::ClassSetItem::Range(_)
            | ast::ClassSetItem::Ascii(_)
            | ast::ClassSetItem::Unicode(_)
            | ast::ClassSetItem::Perl(_) => {
                // These are all base cases, so we don't increment depth.
12
                return Ok(());
            }
            ast::ClassSetItem::Bracketed(ref x) => &x.span,
2
            ast::ClassSetItem::Union(ref x) => &x.span,
        };
2
        self.increment_depth(span)
14
    }
14
    fn visit_class_set_item_post(
14
        &mut self,
14
        ast: &ast::ClassSetItem,
14
    ) -> Result<()> {
14
        match *ast {
            ast::ClassSetItem::Empty(_)
            | ast::ClassSetItem::Literal(_)
            | ast::ClassSetItem::Range(_)
            | ast::ClassSetItem::Ascii(_)
            | ast::ClassSetItem::Unicode(_)
            | ast::ClassSetItem::Perl(_) => {
                // These are all base cases, so we don't decrement depth.
12
                Ok(())
            }
            ast::ClassSetItem::Bracketed(_) | ast::ClassSetItem::Union(_) => {
2
                self.decrement_depth();
2
                Ok(())
            }
        }
14
    }
    fn visit_class_set_binary_op_pre(
        &mut self,
        ast: &ast::ClassSetBinaryOp,
    ) -> Result<()> {
        self.increment_depth(&ast.span)
    }
    fn visit_class_set_binary_op_post(
        &mut self,
        _ast: &ast::ClassSetBinaryOp,
    ) -> Result<()> {
        self.decrement_depth();
        Ok(())
    }
}
/// When the result is an error, transforms the ast::ErrorKind from the source
/// Result into another one. This function is used to return clearer error
/// messages when possible.
4
fn specialize_err<T>(
4
    result: Result<T>,
4
    from: ast::ErrorKind,
4
    to: ast::ErrorKind,
4
) -> Result<T> {
4
    if let Err(e) = result {
        if e.kind == from {
            Err(ast::Error { kind: to, pattern: e.pattern, span: e.span })
        } else {
            Err(e)
        }
    } else {
4
        result
    }
4
}
#[cfg(test)]
mod tests {
    use core::ops::Range;
    use alloc::format;
    use crate::ast::{self, Ast, Position, Span};
    use super::*;
    // Our own assert_eq, which has slightly better formatting (but honestly
    // still kind of crappy).
    macro_rules! assert_eq {
        ($left:expr, $right:expr) => {{
            match (&$left, &$right) {
                (left_val, right_val) => {
                    if !(*left_val == *right_val) {
                        panic!(
                            "assertion failed: `(left == right)`\n\n\
                             left:  `{:?}`\nright: `{:?}`\n\n",
                            left_val, right_val
                        )
                    }
                }
            }
        }};
    }
    // We create these errors to compare with real ast::Errors in the tests.
    // We define equality between TestError and ast::Error to disregard the
    // pattern string in ast::Error, which is annoying to provide in tests.
    #[derive(Clone, Debug)]
    struct TestError {
        span: Span,
        kind: ast::ErrorKind,
    }
    impl PartialEq<ast::Error> for TestError {
        fn eq(&self, other: &ast::Error) -> bool {
            self.span == other.span && self.kind == other.kind
        }
    }
    impl PartialEq<TestError> for ast::Error {
        fn eq(&self, other: &TestError) -> bool {
            self.span == other.span && self.kind == other.kind
        }
    }
    fn s(str: &str) -> String {
        str.to_string()
    }
    fn parser(pattern: &str) -> ParserI<'_, Parser> {
        ParserI::new(Parser::new(), pattern)
    }
    fn parser_octal(pattern: &str) -> ParserI<'_, Parser> {
        let parser = ParserBuilder::new().octal(true).build();
        ParserI::new(parser, pattern)
    }
    fn parser_nest_limit(
        pattern: &str,
        nest_limit: u32,
    ) -> ParserI<'_, Parser> {
        let p = ParserBuilder::new().nest_limit(nest_limit).build();
        ParserI::new(p, pattern)
    }
    fn parser_ignore_whitespace(pattern: &str) -> ParserI<'_, Parser> {
        let p = ParserBuilder::new().ignore_whitespace(true).build();
        ParserI::new(p, pattern)
    }
    /// Short alias for creating a new span.
    fn nspan(start: Position, end: Position) -> Span {
        Span::new(start, end)
    }
    /// Short alias for creating a new position.
    fn npos(offset: usize, line: usize, column: usize) -> Position {
        Position::new(offset, line, column)
    }
    /// Create a new span from the given offset range. This assumes a single
    /// line and sets the columns based on the offsets. i.e., This only works
    /// out of the box for ASCII, which is fine for most tests.
    fn span(range: Range<usize>) -> Span {
        let start = Position::new(range.start, 1, range.start + 1);
        let end = Position::new(range.end, 1, range.end + 1);
        Span::new(start, end)
    }
    /// Create a new span for the corresponding byte range in the given string.
    fn span_range(subject: &str, range: Range<usize>) -> Span {
        let start = Position {
            offset: range.start,
            line: 1 + subject[..range.start].matches('\n').count(),
            column: 1 + subject[..range.start]
                .chars()
                .rev()
                .position(|c| c == '\n')
                .unwrap_or(subject[..range.start].chars().count()),
        };
        let end = Position {
            offset: range.end,
            line: 1 + subject[..range.end].matches('\n').count(),
            column: 1 + subject[..range.end]
                .chars()
                .rev()
                .position(|c| c == '\n')
                .unwrap_or(subject[..range.end].chars().count()),
        };
        Span::new(start, end)
    }
    /// Create a verbatim literal starting at the given position.
    fn lit(c: char, start: usize) -> Ast {
        lit_with(c, span(start..start + c.len_utf8()))
    }
    /// Create a meta literal starting at the given position.
    fn meta_lit(c: char, span: Span) -> Ast {
        Ast::literal(ast::Literal { span, kind: ast::LiteralKind::Meta, c })
    }
    /// Create a verbatim literal with the given span.
    fn lit_with(c: char, span: Span) -> Ast {
        Ast::literal(ast::Literal {
            span,
            kind: ast::LiteralKind::Verbatim,
            c,
        })
    }
    /// Create a concatenation with the given range.
    fn concat(range: Range<usize>, asts: Vec<Ast>) -> Ast {
        concat_with(span(range), asts)
    }
    /// Create a concatenation with the given span.
    fn concat_with(span: Span, asts: Vec<Ast>) -> Ast {
        Ast::concat(ast::Concat { span, asts })
    }
    /// Create an alternation with the given span.
    fn alt(range: Range<usize>, asts: Vec<Ast>) -> Ast {
        Ast::alternation(ast::Alternation { span: span(range), asts })
    }
    /// Create a capturing group with the given span.
    fn group(range: Range<usize>, index: u32, ast: Ast) -> Ast {
        Ast::group(ast::Group {
            span: span(range),
            kind: ast::GroupKind::CaptureIndex(index),
            ast: Box::new(ast),
        })
    }
    /// Create an ast::SetFlags.
    ///
    /// The given pattern should be the full pattern string. The range given
    /// should correspond to the byte offsets where the flag set occurs.
    ///
    /// If negated is true, then the set is interpreted as beginning with a
    /// negation.
    fn flag_set(
        pat: &str,
        range: Range<usize>,
        flag: ast::Flag,
        negated: bool,
    ) -> Ast {
        let mut items = vec![ast::FlagsItem {
            span: span_range(pat, (range.end - 2)..(range.end - 1)),
            kind: ast::FlagsItemKind::Flag(flag),
        }];
        if negated {
            items.insert(
                0,
                ast::FlagsItem {
                    span: span_range(pat, (range.start + 2)..(range.end - 2)),
                    kind: ast::FlagsItemKind::Negation,
                },
            );
        }
        Ast::flags(ast::SetFlags {
            span: span_range(pat, range.clone()),
            flags: ast::Flags {
                span: span_range(pat, (range.start + 2)..(range.end - 1)),
                items,
            },
        })
    }
    #[test]
    fn parse_nest_limit() {
        // A nest limit of 0 still allows some types of regexes.
        assert_eq!(
            parser_nest_limit("", 0).parse(),
            Ok(Ast::empty(span(0..0)))
        );
        assert_eq!(parser_nest_limit("a", 0).parse(), Ok(lit('a', 0)));
        // Test repetition operations, which require one level of nesting.
        assert_eq!(
            parser_nest_limit("a+", 0).parse().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::NestLimitExceeded(0),
            }
        );
        assert_eq!(
            parser_nest_limit("a+", 1).parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..2),
                op: ast::RepetitionOp {
                    span: span(1..2),
                    kind: ast::RepetitionKind::OneOrMore,
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser_nest_limit("(a)+", 1).parse().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::NestLimitExceeded(1),
            }
        );
        assert_eq!(
            parser_nest_limit("a+*", 1).parse().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::NestLimitExceeded(1),
            }
        );
        assert_eq!(
            parser_nest_limit("a+*", 2).parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..3),
                op: ast::RepetitionOp {
                    span: span(2..3),
                    kind: ast::RepetitionKind::ZeroOrMore,
                },
                greedy: true,
                ast: Box::new(Ast::repetition(ast::Repetition {
                    span: span(0..2),
                    op: ast::RepetitionOp {
                        span: span(1..2),
                        kind: ast::RepetitionKind::OneOrMore,
                    },
                    greedy: true,
                    ast: Box::new(lit('a', 0)),
                })),
            }))
        );
        // Test concatenations. A concatenation requires one level of nesting.
        assert_eq!(
            parser_nest_limit("ab", 0).parse().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::NestLimitExceeded(0),
            }
        );
        assert_eq!(
            parser_nest_limit("ab", 1).parse(),
            Ok(concat(0..2, vec![lit('a', 0), lit('b', 1)]))
        );
        assert_eq!(
            parser_nest_limit("abc", 1).parse(),
            Ok(concat(0..3, vec![lit('a', 0), lit('b', 1), lit('c', 2)]))
        );
        // Test alternations. An alternation requires one level of nesting.
        assert_eq!(
            parser_nest_limit("a|b", 0).parse().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::NestLimitExceeded(0),
            }
        );
        assert_eq!(
            parser_nest_limit("a|b", 1).parse(),
            Ok(alt(0..3, vec![lit('a', 0), lit('b', 2)]))
        );
        assert_eq!(
            parser_nest_limit("a|b|c", 1).parse(),
            Ok(alt(0..5, vec![lit('a', 0), lit('b', 2), lit('c', 4)]))
        );
        // Test character classes. Classes form their own mini-recursive
        // syntax!
        assert_eq!(
            parser_nest_limit("[a]", 0).parse().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::NestLimitExceeded(0),
            }
        );
        assert_eq!(
            parser_nest_limit("[a]", 1).parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..3),
                negated: false,
                kind: ast::ClassSet::Item(ast::ClassSetItem::Literal(
                    ast::Literal {
                        span: span(1..2),
                        kind: ast::LiteralKind::Verbatim,
                        c: 'a',
                    }
                )),
            }))
        );
        assert_eq!(
            parser_nest_limit("[ab]", 1).parse().unwrap_err(),
            TestError {
                span: span(1..3),
                kind: ast::ErrorKind::NestLimitExceeded(1),
            }
        );
        assert_eq!(
            parser_nest_limit("[ab[cd]]", 2).parse().unwrap_err(),
            TestError {
                span: span(3..7),
                kind: ast::ErrorKind::NestLimitExceeded(2),
            }
        );
        assert_eq!(
            parser_nest_limit("[ab[cd]]", 3).parse().unwrap_err(),
            TestError {
                span: span(4..6),
                kind: ast::ErrorKind::NestLimitExceeded(3),
            }
        );
        assert_eq!(
            parser_nest_limit("[a--b]", 1).parse().unwrap_err(),
            TestError {
                span: span(1..5),
                kind: ast::ErrorKind::NestLimitExceeded(1),
            }
        );
        assert_eq!(
            parser_nest_limit("[a--bc]", 2).parse().unwrap_err(),
            TestError {
                span: span(4..6),
                kind: ast::ErrorKind::NestLimitExceeded(2),
            }
        );
    }
    #[test]
    fn parse_comments() {
        let pat = "(?x)
# This is comment 1.
foo # This is comment 2.
  # This is comment 3.
bar
# This is comment 4.";
        let astc = parser(pat).parse_with_comments().unwrap();
        assert_eq!(
            astc.ast,
            concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    lit_with('f', span_range(pat, 26..27)),
                    lit_with('o', span_range(pat, 27..28)),
                    lit_with('o', span_range(pat, 28..29)),
                    lit_with('b', span_range(pat, 74..75)),
                    lit_with('a', span_range(pat, 75..76)),
                    lit_with('r', span_range(pat, 76..77)),
                ]
            )
        );
        assert_eq!(
            astc.comments,
            vec![
                ast::Comment {
                    span: span_range(pat, 5..26),
                    comment: s(" This is comment 1."),
                },
                ast::Comment {
                    span: span_range(pat, 30..51),
                    comment: s(" This is comment 2."),
                },
                ast::Comment {
                    span: span_range(pat, 53..74),
                    comment: s(" This is comment 3."),
                },
                ast::Comment {
                    span: span_range(pat, 78..98),
                    comment: s(" This is comment 4."),
                },
            ]
        );
    }
    #[test]
    fn parse_holistic() {
        assert_eq!(parser("]").parse(), Ok(lit(']', 0)));
        assert_eq!(
            parser(r"\\\.\+\*\?\(\)\|\[\]\{\}\^\$\#\&\-\~").parse(),
            Ok(concat(
                0..36,
                vec![
                    meta_lit('\\', span(0..2)),
                    meta_lit('.', span(2..4)),
                    meta_lit('+', span(4..6)),
                    meta_lit('*', span(6..8)),
                    meta_lit('?', span(8..10)),
                    meta_lit('(', span(10..12)),
                    meta_lit(')', span(12..14)),
                    meta_lit('|', span(14..16)),
                    meta_lit('[', span(16..18)),
                    meta_lit(']', span(18..20)),
                    meta_lit('{', span(20..22)),
                    meta_lit('}', span(22..24)),
                    meta_lit('^', span(24..26)),
                    meta_lit('$', span(26..28)),
                    meta_lit('#', span(28..30)),
                    meta_lit('&', span(30..32)),
                    meta_lit('-', span(32..34)),
                    meta_lit('~', span(34..36)),
                ]
            ))
        );
    }
    #[test]
    fn parse_ignore_whitespace() {
        // Test that basic whitespace insensitivity works.
        let pat = "(?x)a b";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                nspan(npos(0, 1, 1), npos(7, 1, 8)),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
                    lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
                ]
            ))
        );
        // Test that we can toggle whitespace insensitivity.
        let pat = "(?x)a b(?-x)a b";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                nspan(npos(0, 1, 1), npos(15, 1, 16)),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
                    lit_with('b', nspan(npos(6, 1, 7), npos(7, 1, 8))),
                    flag_set(pat, 7..12, ast::Flag::IgnoreWhitespace, true),
                    lit_with('a', nspan(npos(12, 1, 13), npos(13, 1, 14))),
                    lit_with(' ', nspan(npos(13, 1, 14), npos(14, 1, 15))),
                    lit_with('b', nspan(npos(14, 1, 15), npos(15, 1, 16))),
                ]
            ))
        );
        // Test that nesting whitespace insensitive flags works.
        let pat = "a (?x:a )a ";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..11),
                vec![
                    lit_with('a', span_range(pat, 0..1)),
                    lit_with(' ', span_range(pat, 1..2)),
                    Ast::group(ast::Group {
                        span: span_range(pat, 2..9),
                        kind: ast::GroupKind::NonCapturing(ast::Flags {
                            span: span_range(pat, 4..5),
                            items: vec![ast::FlagsItem {
                                span: span_range(pat, 4..5),
                                kind: ast::FlagsItemKind::Flag(
                                    ast::Flag::IgnoreWhitespace
                                ),
                            },],
                        }),
                        ast: Box::new(lit_with('a', span_range(pat, 6..7))),
                    }),
                    lit_with('a', span_range(pat, 9..10)),
                    lit_with(' ', span_range(pat, 10..11)),
                ]
            ))
        );
        // Test that whitespace after an opening paren is insignificant.
        let pat = "(?x)( ?P<foo> a )";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    Ast::group(ast::Group {
                        span: span_range(pat, 4..pat.len()),
                        kind: ast::GroupKind::CaptureName {
                            starts_with_p: true,
                            name: ast::CaptureName {
                                span: span_range(pat, 9..12),
                                name: s("foo"),
                                index: 1,
                            }
                        },
                        ast: Box::new(lit_with('a', span_range(pat, 14..15))),
                    }),
                ]
            ))
        );
        let pat = "(?x)(  a )";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    Ast::group(ast::Group {
                        span: span_range(pat, 4..pat.len()),
                        kind: ast::GroupKind::CaptureIndex(1),
                        ast: Box::new(lit_with('a', span_range(pat, 7..8))),
                    }),
                ]
            ))
        );
        let pat = "(?x)(  ?:  a )";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    Ast::group(ast::Group {
                        span: span_range(pat, 4..pat.len()),
                        kind: ast::GroupKind::NonCapturing(ast::Flags {
                            span: span_range(pat, 8..8),
                            items: vec![],
                        }),
                        ast: Box::new(lit_with('a', span_range(pat, 11..12))),
                    }),
                ]
            ))
        );
        let pat = r"(?x)\x { 53 }";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    Ast::literal(ast::Literal {
                        span: span(4..13),
                        kind: ast::LiteralKind::HexBrace(
                            ast::HexLiteralKind::X
                        ),
                        c: 'S',
                    }),
                ]
            ))
        );
        // Test that whitespace after an escape is OK.
        let pat = r"(?x)\ ";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    flag_set(pat, 0..4, ast::Flag::IgnoreWhitespace, false),
                    Ast::literal(ast::Literal {
                        span: span_range(pat, 4..6),
                        kind: ast::LiteralKind::Superfluous,
                        c: ' ',
                    }),
                ]
            ))
        );
    }
    #[test]
    fn parse_newlines() {
        let pat = ".\n.";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..3),
                vec![
                    Ast::dot(span_range(pat, 0..1)),
                    lit_with('\n', span_range(pat, 1..2)),
                    Ast::dot(span_range(pat, 2..3)),
                ]
            ))
        );
        let pat = "foobar\nbaz\nquux\n";
        assert_eq!(
            parser(pat).parse(),
            Ok(concat_with(
                span_range(pat, 0..pat.len()),
                vec![
                    lit_with('f', nspan(npos(0, 1, 1), npos(1, 1, 2))),
                    lit_with('o', nspan(npos(1, 1, 2), npos(2, 1, 3))),
                    lit_with('o', nspan(npos(2, 1, 3), npos(3, 1, 4))),
                    lit_with('b', nspan(npos(3, 1, 4), npos(4, 1, 5))),
                    lit_with('a', nspan(npos(4, 1, 5), npos(5, 1, 6))),
                    lit_with('r', nspan(npos(5, 1, 6), npos(6, 1, 7))),
                    lit_with('\n', nspan(npos(6, 1, 7), npos(7, 2, 1))),
                    lit_with('b', nspan(npos(7, 2, 1), npos(8, 2, 2))),
                    lit_with('a', nspan(npos(8, 2, 2), npos(9, 2, 3))),
                    lit_with('z', nspan(npos(9, 2, 3), npos(10, 2, 4))),
                    lit_with('\n', nspan(npos(10, 2, 4), npos(11, 3, 1))),
                    lit_with('q', nspan(npos(11, 3, 1), npos(12, 3, 2))),
                    lit_with('u', nspan(npos(12, 3, 2), npos(13, 3, 3))),
                    lit_with('u', nspan(npos(13, 3, 3), npos(14, 3, 4))),
                    lit_with('x', nspan(npos(14, 3, 4), npos(15, 3, 5))),
                    lit_with('\n', nspan(npos(15, 3, 5), npos(16, 4, 1))),
                ]
            ))
        );
    }
    #[test]
    fn parse_uncounted_repetition() {
        assert_eq!(
            parser(r"a*").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..2),
                op: ast::RepetitionOp {
                    span: span(1..2),
                    kind: ast::RepetitionKind::ZeroOrMore,
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a+").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..2),
                op: ast::RepetitionOp {
                    span: span(1..2),
                    kind: ast::RepetitionKind::OneOrMore,
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a?").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..2),
                op: ast::RepetitionOp {
                    span: span(1..2),
                    kind: ast::RepetitionKind::ZeroOrOne,
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a??").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..3),
                op: ast::RepetitionOp {
                    span: span(1..3),
                    kind: ast::RepetitionKind::ZeroOrOne,
                },
                greedy: false,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a?").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..2),
                op: ast::RepetitionOp {
                    span: span(1..2),
                    kind: ast::RepetitionKind::ZeroOrOne,
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a?b").parse(),
            Ok(concat(
                0..3,
                vec![
                    Ast::repetition(ast::Repetition {
                        span: span(0..2),
                        op: ast::RepetitionOp {
                            span: span(1..2),
                            kind: ast::RepetitionKind::ZeroOrOne,
                        },
                        greedy: true,
                        ast: Box::new(lit('a', 0)),
                    }),
                    lit('b', 2),
                ]
            ))
        );
        assert_eq!(
            parser(r"a??b").parse(),
            Ok(concat(
                0..4,
                vec![
                    Ast::repetition(ast::Repetition {
                        span: span(0..3),
                        op: ast::RepetitionOp {
                            span: span(1..3),
                            kind: ast::RepetitionKind::ZeroOrOne,
                        },
                        greedy: false,
                        ast: Box::new(lit('a', 0)),
                    }),
                    lit('b', 3),
                ]
            ))
        );
        assert_eq!(
            parser(r"ab?").parse(),
            Ok(concat(
                0..3,
                vec![
                    lit('a', 0),
                    Ast::repetition(ast::Repetition {
                        span: span(1..3),
                        op: ast::RepetitionOp {
                            span: span(2..3),
                            kind: ast::RepetitionKind::ZeroOrOne,
                        },
                        greedy: true,
                        ast: Box::new(lit('b', 1)),
                    }),
                ]
            ))
        );
        assert_eq!(
            parser(r"(ab)?").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..5),
                op: ast::RepetitionOp {
                    span: span(4..5),
                    kind: ast::RepetitionKind::ZeroOrOne,
                },
                greedy: true,
                ast: Box::new(group(
                    0..4,
                    1,
                    concat(1..3, vec![lit('a', 1), lit('b', 2),])
                )),
            }))
        );
        assert_eq!(
            parser(r"|a?").parse(),
            Ok(alt(
                0..3,
                vec![
                    Ast::empty(span(0..0)),
                    Ast::repetition(ast::Repetition {
                        span: span(1..3),
                        op: ast::RepetitionOp {
                            span: span(2..3),
                            kind: ast::RepetitionKind::ZeroOrOne,
                        },
                        greedy: true,
                        ast: Box::new(lit('a', 1)),
                    }),
                ]
            ))
        );
        assert_eq!(
            parser(r"*").parse().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"(?i)*").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"(*)").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"(?:?)").parse().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"+").parse().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"?").parse().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"(?)").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"|*").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"|+").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"|?").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
    }
    #[test]
    fn parse_counted_repetition() {
        assert_eq!(
            parser(r"a{5}").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..4),
                op: ast::RepetitionOp {
                    span: span(1..4),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Exactly(5)
                    ),
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a{5,}").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..5),
                op: ast::RepetitionOp {
                    span: span(1..5),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::AtLeast(5)
                    ),
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a{5,9}").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..6),
                op: ast::RepetitionOp {
                    span: span(1..6),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Bounded(5, 9)
                    ),
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a{5}?").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..5),
                op: ast::RepetitionOp {
                    span: span(1..5),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Exactly(5)
                    ),
                },
                greedy: false,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"ab{5}").parse(),
            Ok(concat(
                0..5,
                vec![
                    lit('a', 0),
                    Ast::repetition(ast::Repetition {
                        span: span(1..5),
                        op: ast::RepetitionOp {
                            span: span(2..5),
                            kind: ast::RepetitionKind::Range(
                                ast::RepetitionRange::Exactly(5)
                            ),
                        },
                        greedy: true,
                        ast: Box::new(lit('b', 1)),
                    }),
                ]
            ))
        );
        assert_eq!(
            parser(r"ab{5}c").parse(),
            Ok(concat(
                0..6,
                vec![
                    lit('a', 0),
                    Ast::repetition(ast::Repetition {
                        span: span(1..5),
                        op: ast::RepetitionOp {
                            span: span(2..5),
                            kind: ast::RepetitionKind::Range(
                                ast::RepetitionRange::Exactly(5)
                            ),
                        },
                        greedy: true,
                        ast: Box::new(lit('b', 1)),
                    }),
                    lit('c', 5),
                ]
            ))
        );
        assert_eq!(
            parser(r"a{ 5 }").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..6),
                op: ast::RepetitionOp {
                    span: span(1..6),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Exactly(5)
                    ),
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"a{ 5 , 9 }").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..10),
                op: ast::RepetitionOp {
                    span: span(1..10),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Bounded(5, 9)
                    ),
                },
                greedy: true,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser_ignore_whitespace(r"a{5,9} ?").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..8),
                op: ast::RepetitionOp {
                    span: span(1..8),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Bounded(5, 9)
                    ),
                },
                greedy: false,
                ast: Box::new(lit('a', 0)),
            }))
        );
        assert_eq!(
            parser(r"\b{5,9}").parse(),
            Ok(Ast::repetition(ast::Repetition {
                span: span(0..7),
                op: ast::RepetitionOp {
                    span: span(2..7),
                    kind: ast::RepetitionKind::Range(
                        ast::RepetitionRange::Bounded(5, 9)
                    ),
                },
                greedy: true,
                ast: Box::new(Ast::assertion(ast::Assertion {
                    span: span(0..2),
                    kind: ast::AssertionKind::WordBoundary,
                })),
            }))
        );
        assert_eq!(
            parser(r"(?i){0}").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"(?m){1,1}").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"a{]}").parse().unwrap_err(),
            TestError {
                span: span(2..2),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        assert_eq!(
            parser(r"a{1,]}").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        assert_eq!(
            parser(r"a{").parse().unwrap_err(),
            TestError {
                span: span(1..2),
                kind: ast::ErrorKind::RepetitionCountUnclosed,
            }
        );
        assert_eq!(
            parser(r"a{}").parse().unwrap_err(),
            TestError {
                span: span(2..2),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        assert_eq!(
            parser(r"a{a").parse().unwrap_err(),
            TestError {
                span: span(2..2),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        assert_eq!(
            parser(r"a{9999999999}").parse().unwrap_err(),
            TestError {
                span: span(2..12),
                kind: ast::ErrorKind::DecimalInvalid,
            }
        );
        assert_eq!(
            parser(r"a{9").parse().unwrap_err(),
            TestError {
                span: span(1..3),
                kind: ast::ErrorKind::RepetitionCountUnclosed,
            }
        );
        assert_eq!(
            parser(r"a{9,a").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        assert_eq!(
            parser(r"a{9,9999999999}").parse().unwrap_err(),
            TestError {
                span: span(4..14),
                kind: ast::ErrorKind::DecimalInvalid,
            }
        );
        assert_eq!(
            parser(r"a{9,").parse().unwrap_err(),
            TestError {
                span: span(1..4),
                kind: ast::ErrorKind::RepetitionCountUnclosed,
            }
        );
        assert_eq!(
            parser(r"a{9,11").parse().unwrap_err(),
            TestError {
                span: span(1..6),
                kind: ast::ErrorKind::RepetitionCountUnclosed,
            }
        );
        assert_eq!(
            parser(r"a{2,1}").parse().unwrap_err(),
            TestError {
                span: span(1..6),
                kind: ast::ErrorKind::RepetitionCountInvalid,
            }
        );
        assert_eq!(
            parser(r"{5}").parse().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
        assert_eq!(
            parser(r"|{5}").parse().unwrap_err(),
            TestError {
                span: span(1..1),
                kind: ast::ErrorKind::RepetitionMissing,
            }
        );
    }
    #[test]
    fn parse_alternate() {
        assert_eq!(
            parser(r"a|b").parse(),
            Ok(Ast::alternation(ast::Alternation {
                span: span(0..3),
                asts: vec![lit('a', 0), lit('b', 2)],
            }))
        );
        assert_eq!(
            parser(r"(a|b)").parse(),
            Ok(group(
                0..5,
                1,
                Ast::alternation(ast::Alternation {
                    span: span(1..4),
                    asts: vec![lit('a', 1), lit('b', 3)],
                })
            ))
        );
        assert_eq!(
            parser(r"a|b|c").parse(),
            Ok(Ast::alternation(ast::Alternation {
                span: span(0..5),
                asts: vec![lit('a', 0), lit('b', 2), lit('c', 4)],
            }))
        );
        assert_eq!(
            parser(r"ax|by|cz").parse(),
            Ok(Ast::alternation(ast::Alternation {
                span: span(0..8),
                asts: vec![
                    concat(0..2, vec![lit('a', 0), lit('x', 1)]),
                    concat(3..5, vec![lit('b', 3), lit('y', 4)]),
                    concat(6..8, vec![lit('c', 6), lit('z', 7)]),
                ],
            }))
        );
        assert_eq!(
            parser(r"(ax|by|cz)").parse(),
            Ok(group(
                0..10,
                1,
                Ast::alternation(ast::Alternation {
                    span: span(1..9),
                    asts: vec![
                        concat(1..3, vec![lit('a', 1), lit('x', 2)]),
                        concat(4..6, vec![lit('b', 4), lit('y', 5)]),
                        concat(7..9, vec![lit('c', 7), lit('z', 8)]),
                    ],
                })
            ))
        );
        assert_eq!(
            parser(r"(ax|(by|(cz)))").parse(),
            Ok(group(
                0..14,
                1,
                alt(
                    1..13,
                    vec![
                        concat(1..3, vec![lit('a', 1), lit('x', 2)]),
                        group(
                            4..13,
                            2,
                            alt(
                                5..12,
                                vec![
                                    concat(
                                        5..7,
                                        vec![lit('b', 5), lit('y', 6)]
                                    ),
                                    group(
                                        8..12,
                                        3,
                                        concat(
                                            9..11,
                                            vec![lit('c', 9), lit('z', 10),]
                                        )
                                    ),
                                ]
                            )
                        ),
                    ]
                )
            ))
        );
        assert_eq!(
            parser(r"|").parse(),
            Ok(alt(
                0..1,
                vec![Ast::empty(span(0..0)), Ast::empty(span(1..1)),]
            ))
        );
        assert_eq!(
            parser(r"||").parse(),
            Ok(alt(
                0..2,
                vec![
                    Ast::empty(span(0..0)),
                    Ast::empty(span(1..1)),
                    Ast::empty(span(2..2)),
                ]
            ))
        );
        assert_eq!(
            parser(r"a|").parse(),
            Ok(alt(0..2, vec![lit('a', 0), Ast::empty(span(2..2)),]))
        );
        assert_eq!(
            parser(r"|a").parse(),
            Ok(alt(0..2, vec![Ast::empty(span(0..0)), lit('a', 1),]))
        );
        assert_eq!(
            parser(r"(|)").parse(),
            Ok(group(
                0..3,
                1,
                alt(
                    1..2,
                    vec![Ast::empty(span(1..1)), Ast::empty(span(2..2)),]
                )
            ))
        );
        assert_eq!(
            parser(r"(a|)").parse(),
            Ok(group(
                0..4,
                1,
                alt(1..3, vec![lit('a', 1), Ast::empty(span(3..3)),])
            ))
        );
        assert_eq!(
            parser(r"(|a)").parse(),
            Ok(group(
                0..4,
                1,
                alt(1..3, vec![Ast::empty(span(1..1)), lit('a', 2),])
            ))
        );
        assert_eq!(
            parser(r"a|b)").parse().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::GroupUnopened,
            }
        );
        assert_eq!(
            parser(r"(a|b").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnclosed,
            }
        );
    }
    #[test]
    fn parse_unsupported_lookaround() {
        assert_eq!(
            parser(r"(?=a)").parse().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::UnsupportedLookAround,
            }
        );
        assert_eq!(
            parser(r"(?!a)").parse().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::UnsupportedLookAround,
            }
        );
        assert_eq!(
            parser(r"(?<=a)").parse().unwrap_err(),
            TestError {
                span: span(0..4),
                kind: ast::ErrorKind::UnsupportedLookAround,
            }
        );
        assert_eq!(
            parser(r"(?<!a)").parse().unwrap_err(),
            TestError {
                span: span(0..4),
                kind: ast::ErrorKind::UnsupportedLookAround,
            }
        );
    }
    #[test]
    fn parse_group() {
        assert_eq!(
            parser("(?i)").parse(),
            Ok(Ast::flags(ast::SetFlags {
                span: span(0..4),
                flags: ast::Flags {
                    span: span(2..3),
                    items: vec![ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    }],
                },
            }))
        );
        assert_eq!(
            parser("(?iU)").parse(),
            Ok(Ast::flags(ast::SetFlags {
                span: span(0..5),
                flags: ast::Flags {
                    span: span(2..4),
                    items: vec![
                        ast::FlagsItem {
                            span: span(2..3),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::CaseInsensitive
                            ),
                        },
                        ast::FlagsItem {
                            span: span(3..4),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::SwapGreed
                            ),
                        },
                    ],
                },
            }))
        );
        assert_eq!(
            parser("(?i-U)").parse(),
            Ok(Ast::flags(ast::SetFlags {
                span: span(0..6),
                flags: ast::Flags {
                    span: span(2..5),
                    items: vec![
                        ast::FlagsItem {
                            span: span(2..3),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::CaseInsensitive
                            ),
                        },
                        ast::FlagsItem {
                            span: span(3..4),
                            kind: ast::FlagsItemKind::Negation,
                        },
                        ast::FlagsItem {
                            span: span(4..5),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::SwapGreed
                            ),
                        },
                    ],
                },
            }))
        );
        assert_eq!(
            parser("()").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..2),
                kind: ast::GroupKind::CaptureIndex(1),
                ast: Box::new(Ast::empty(span(1..1))),
            }))
        );
        assert_eq!(
            parser("(a)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..3),
                kind: ast::GroupKind::CaptureIndex(1),
                ast: Box::new(lit('a', 1)),
            }))
        );
        assert_eq!(
            parser("(())").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..4),
                kind: ast::GroupKind::CaptureIndex(1),
                ast: Box::new(Ast::group(ast::Group {
                    span: span(1..3),
                    kind: ast::GroupKind::CaptureIndex(2),
                    ast: Box::new(Ast::empty(span(2..2))),
                })),
            }))
        );
        assert_eq!(
            parser("(?:a)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..5),
                kind: ast::GroupKind::NonCapturing(ast::Flags {
                    span: span(2..2),
                    items: vec![],
                }),
                ast: Box::new(lit('a', 3)),
            }))
        );
        assert_eq!(
            parser("(?i:a)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..6),
                kind: ast::GroupKind::NonCapturing(ast::Flags {
                    span: span(2..3),
                    items: vec![ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    },],
                }),
                ast: Box::new(lit('a', 4)),
            }))
        );
        assert_eq!(
            parser("(?i-U:a)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..8),
                kind: ast::GroupKind::NonCapturing(ast::Flags {
                    span: span(2..5),
                    items: vec![
                        ast::FlagsItem {
                            span: span(2..3),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::CaseInsensitive
                            ),
                        },
                        ast::FlagsItem {
                            span: span(3..4),
                            kind: ast::FlagsItemKind::Negation,
                        },
                        ast::FlagsItem {
                            span: span(4..5),
                            kind: ast::FlagsItemKind::Flag(
                                ast::Flag::SwapGreed
                            ),
                        },
                    ],
                }),
                ast: Box::new(lit('a', 6)),
            }))
        );
        assert_eq!(
            parser("(").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnclosed,
            }
        );
        assert_eq!(
            parser("(?").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnclosed,
            }
        );
        assert_eq!(
            parser("(?P").parse().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::FlagUnrecognized,
            }
        );
        assert_eq!(
            parser("(?P<").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::GroupNameUnexpectedEof,
            }
        );
        assert_eq!(
            parser("(a").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnclosed,
            }
        );
        assert_eq!(
            parser("(()").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnclosed,
            }
        );
        assert_eq!(
            parser(")").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::GroupUnopened,
            }
        );
        assert_eq!(
            parser("a)").parse().unwrap_err(),
            TestError {
                span: span(1..2),
                kind: ast::ErrorKind::GroupUnopened,
            }
        );
    }
    #[test]
    fn parse_capture_name() {
        assert_eq!(
            parser("(?<a>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..7),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: false,
                    name: ast::CaptureName {
                        span: span(3..4),
                        name: s("a"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 5)),
            }))
        );
        assert_eq!(
            parser("(?P<a>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..8),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: span(4..5),
                        name: s("a"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 6)),
            }))
        );
        assert_eq!(
            parser("(?P<abc>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..10),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: span(4..7),
                        name: s("abc"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 8)),
            }))
        );
        assert_eq!(
            parser("(?P<a_1>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..10),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: span(4..7),
                        name: s("a_1"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 8)),
            }))
        );
        assert_eq!(
            parser("(?P<a.1>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..10),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: span(4..7),
                        name: s("a.1"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 8)),
            }))
        );
        assert_eq!(
            parser("(?P<a[1]>z)").parse(),
            Ok(Ast::group(ast::Group {
                span: span(0..11),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: span(4..8),
                        name: s("a[1]"),
                        index: 1,
                    }
                },
                ast: Box::new(lit('z', 9)),
            }))
        );
        assert_eq!(
            parser("(?P<a¾>)").parse(),
            Ok(Ast::group(ast::Group {
                span: Span::new(
                    Position::new(0, 1, 1),
                    Position::new(9, 1, 9),
                ),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: Span::new(
                            Position::new(4, 1, 5),
                            Position::new(7, 1, 7),
                        ),
                        name: s("a¾"),
                        index: 1,
                    }
                },
                ast: Box::new(Ast::empty(Span::new(
                    Position::new(8, 1, 8),
                    Position::new(8, 1, 8),
                ))),
            }))
        );
        assert_eq!(
            parser("(?P<名字>)").parse(),
            Ok(Ast::group(ast::Group {
                span: Span::new(
                    Position::new(0, 1, 1),
                    Position::new(12, 1, 9),
                ),
                kind: ast::GroupKind::CaptureName {
                    starts_with_p: true,
                    name: ast::CaptureName {
                        span: Span::new(
                            Position::new(4, 1, 5),
                            Position::new(10, 1, 7),
                        ),
                        name: s("名字"),
                        index: 1,
                    }
                },
                ast: Box::new(Ast::empty(Span::new(
                    Position::new(11, 1, 8),
                    Position::new(11, 1, 8),
                ))),
            }))
        );
        assert_eq!(
            parser("(?P<").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::GroupNameUnexpectedEof,
            }
        );
        assert_eq!(
            parser("(?P<>z)").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::GroupNameEmpty,
            }
        );
        assert_eq!(
            parser("(?P<a").parse().unwrap_err(),
            TestError {
                span: span(5..5),
                kind: ast::ErrorKind::GroupNameUnexpectedEof,
            }
        );
        assert_eq!(
            parser("(?P<ab").parse().unwrap_err(),
            TestError {
                span: span(6..6),
                kind: ast::ErrorKind::GroupNameUnexpectedEof,
            }
        );
        assert_eq!(
            parser("(?P<0a").parse().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<~").parse().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<abc~").parse().unwrap_err(),
            TestError {
                span: span(7..8),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<a>y)(?P<a>z)").parse().unwrap_err(),
            TestError {
                span: span(12..13),
                kind: ast::ErrorKind::GroupNameDuplicate {
                    original: span(4..5),
                },
            }
        );
        assert_eq!(
            parser("(?P<5>)").parse().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<5a>)").parse().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<¾>)").parse().unwrap_err(),
            TestError {
                span: Span::new(
                    Position::new(4, 1, 5),
                    Position::new(6, 1, 6),
                ),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<¾a>)").parse().unwrap_err(),
            TestError {
                span: Span::new(
                    Position::new(4, 1, 5),
                    Position::new(6, 1, 6),
                ),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<☃>)").parse().unwrap_err(),
            TestError {
                span: Span::new(
                    Position::new(4, 1, 5),
                    Position::new(7, 1, 6),
                ),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
        assert_eq!(
            parser("(?P<a☃>)").parse().unwrap_err(),
            TestError {
                span: Span::new(
                    Position::new(5, 1, 6),
                    Position::new(8, 1, 7),
                ),
                kind: ast::ErrorKind::GroupNameInvalid,
            }
        );
    }
    #[test]
    fn parse_flags() {
        assert_eq!(
            parser("i:").parse_flags(),
            Ok(ast::Flags {
                span: span(0..1),
                items: vec![ast::FlagsItem {
                    span: span(0..1),
                    kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
                }],
            })
        );
        assert_eq!(
            parser("i)").parse_flags(),
            Ok(ast::Flags {
                span: span(0..1),
                items: vec![ast::FlagsItem {
                    span: span(0..1),
                    kind: ast::FlagsItemKind::Flag(ast::Flag::CaseInsensitive),
                }],
            })
        );
        assert_eq!(
            parser("isU:").parse_flags(),
            Ok(ast::Flags {
                span: span(0..3),
                items: vec![
                    ast::FlagsItem {
                        span: span(0..1),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    },
                    ast::FlagsItem {
                        span: span(1..2),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::DotMatchesNewLine
                        ),
                    },
                    ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
                    },
                ],
            })
        );
        assert_eq!(
            parser("-isU:").parse_flags(),
            Ok(ast::Flags {
                span: span(0..4),
                items: vec![
                    ast::FlagsItem {
                        span: span(0..1),
                        kind: ast::FlagsItemKind::Negation,
                    },
                    ast::FlagsItem {
                        span: span(1..2),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    },
                    ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::DotMatchesNewLine
                        ),
                    },
                    ast::FlagsItem {
                        span: span(3..4),
                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
                    },
                ],
            })
        );
        assert_eq!(
            parser("i-sU:").parse_flags(),
            Ok(ast::Flags {
                span: span(0..4),
                items: vec![
                    ast::FlagsItem {
                        span: span(0..1),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    },
                    ast::FlagsItem {
                        span: span(1..2),
                        kind: ast::FlagsItemKind::Negation,
                    },
                    ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::DotMatchesNewLine
                        ),
                    },
                    ast::FlagsItem {
                        span: span(3..4),
                        kind: ast::FlagsItemKind::Flag(ast::Flag::SwapGreed),
                    },
                ],
            })
        );
        assert_eq!(
            parser("i-sR:").parse_flags(),
            Ok(ast::Flags {
                span: span(0..4),
                items: vec![
                    ast::FlagsItem {
                        span: span(0..1),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::CaseInsensitive
                        ),
                    },
                    ast::FlagsItem {
                        span: span(1..2),
                        kind: ast::FlagsItemKind::Negation,
                    },
                    ast::FlagsItem {
                        span: span(2..3),
                        kind: ast::FlagsItemKind::Flag(
                            ast::Flag::DotMatchesNewLine
                        ),
                    },
                    ast::FlagsItem {
                        span: span(3..4),
                        kind: ast::FlagsItemKind::Flag(ast::Flag::CRLF),
                    },
                ],
            })
        );
        assert_eq!(
            parser("isU").parse_flags().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::FlagUnexpectedEof,
            }
        );
        assert_eq!(
            parser("isUa:").parse_flags().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::FlagUnrecognized,
            }
        );
        assert_eq!(
            parser("isUi:").parse_flags().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::FlagDuplicate { original: span(0..1) },
            }
        );
        assert_eq!(
            parser("i-sU-i:").parse_flags().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::FlagRepeatedNegation {
                    original: span(1..2),
                },
            }
        );
        assert_eq!(
            parser("-)").parse_flags().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::FlagDanglingNegation,
            }
        );
        assert_eq!(
            parser("i-)").parse_flags().unwrap_err(),
            TestError {
                span: span(1..2),
                kind: ast::ErrorKind::FlagDanglingNegation,
            }
        );
        assert_eq!(
            parser("iU-)").parse_flags().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::FlagDanglingNegation,
            }
        );
    }
    #[test]
    fn parse_flag() {
        assert_eq!(parser("i").parse_flag(), Ok(ast::Flag::CaseInsensitive));
        assert_eq!(parser("m").parse_flag(), Ok(ast::Flag::MultiLine));
        assert_eq!(parser("s").parse_flag(), Ok(ast::Flag::DotMatchesNewLine));
        assert_eq!(parser("U").parse_flag(), Ok(ast::Flag::SwapGreed));
        assert_eq!(parser("u").parse_flag(), Ok(ast::Flag::Unicode));
        assert_eq!(parser("R").parse_flag(), Ok(ast::Flag::CRLF));
        assert_eq!(parser("x").parse_flag(), Ok(ast::Flag::IgnoreWhitespace));
        assert_eq!(
            parser("a").parse_flag().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::FlagUnrecognized,
            }
        );
        assert_eq!(
            parser("☃").parse_flag().unwrap_err(),
            TestError {
                span: span_range("☃", 0..3),
                kind: ast::ErrorKind::FlagUnrecognized,
            }
        );
    }
    #[test]
    fn parse_primitive_non_escape() {
        assert_eq!(
            parser(r".").parse_primitive(),
            Ok(Primitive::Dot(span(0..1)))
        );
        assert_eq!(
            parser(r"^").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..1),
                kind: ast::AssertionKind::StartLine,
            }))
        );
        assert_eq!(
            parser(r"$").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..1),
                kind: ast::AssertionKind::EndLine,
            }))
        );
        assert_eq!(
            parser(r"a").parse_primitive(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..1),
                kind: ast::LiteralKind::Verbatim,
                c: 'a',
            }))
        );
        assert_eq!(
            parser(r"|").parse_primitive(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..1),
                kind: ast::LiteralKind::Verbatim,
                c: '|',
            }))
        );
        assert_eq!(
            parser(r"☃").parse_primitive(),
            Ok(Primitive::Literal(ast::Literal {
                span: span_range("☃", 0..3),
                kind: ast::LiteralKind::Verbatim,
                c: '☃',
            }))
        );
    }
    #[test]
    fn parse_escape() {
        assert_eq!(
            parser(r"\|").parse_primitive(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..2),
                kind: ast::LiteralKind::Meta,
                c: '|',
            }))
        );
        let specials = &[
            (r"\a", '\x07', ast::SpecialLiteralKind::Bell),
            (r"\f", '\x0C', ast::SpecialLiteralKind::FormFeed),
            (r"\t", '\t', ast::SpecialLiteralKind::Tab),
            (r"\n", '\n', ast::SpecialLiteralKind::LineFeed),
            (r"\r", '\r', ast::SpecialLiteralKind::CarriageReturn),
            (r"\v", '\x0B', ast::SpecialLiteralKind::VerticalTab),
        ];
        for &(pat, c, ref kind) in specials {
            assert_eq!(
                parser(pat).parse_primitive(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..2),
                    kind: ast::LiteralKind::Special(kind.clone()),
                    c,
                }))
            );
        }
        assert_eq!(
            parser(r"\A").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::StartText,
            }))
        );
        assert_eq!(
            parser(r"\z").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::EndText,
            }))
        );
        assert_eq!(
            parser(r"\b").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::WordBoundary,
            }))
        );
        assert_eq!(
            parser(r"\b{start}").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..9),
                kind: ast::AssertionKind::WordBoundaryStart,
            }))
        );
        assert_eq!(
            parser(r"\b{end}").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..7),
                kind: ast::AssertionKind::WordBoundaryEnd,
            }))
        );
        assert_eq!(
            parser(r"\b{start-half}").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..14),
                kind: ast::AssertionKind::WordBoundaryStartHalf,
            }))
        );
        assert_eq!(
            parser(r"\b{end-half}").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..12),
                kind: ast::AssertionKind::WordBoundaryEndHalf,
            }))
        );
        assert_eq!(
            parser(r"\<").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::WordBoundaryStartAngle,
            }))
        );
        assert_eq!(
            parser(r"\>").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::WordBoundaryEndAngle,
            }))
        );
        assert_eq!(
            parser(r"\B").parse_primitive(),
            Ok(Primitive::Assertion(ast::Assertion {
                span: span(0..2),
                kind: ast::AssertionKind::NotWordBoundary,
            }))
        );
        // We also support superfluous escapes in most cases now too.
        for c in ['!', '@', '%', '"', '\'', '/', ' '] {
            let pat = format!(r"\{}", c);
            assert_eq!(
                parser(&pat).parse_primitive(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..2),
                    kind: ast::LiteralKind::Superfluous,
                    c,
                }))
            );
        }
        // Some superfluous escapes, namely [0-9A-Za-z], are still banned. This
        // gives flexibility for future evolution.
        assert_eq!(
            parser(r"\e").parse_escape().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::EscapeUnrecognized,
            }
        );
        assert_eq!(
            parser(r"\y").parse_escape().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::EscapeUnrecognized,
            }
        );
        // Starting a special word boundary without any non-whitespace chars
        // after the brace makes it ambiguous whether the user meant to write
        // a counted repetition (probably not?) or an actual special word
        // boundary assertion.
        assert_eq!(
            parser(r"\b{").parse_escape().unwrap_err(),
            TestError {
                span: span(0..3),
                kind: ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
            }
        );
        assert_eq!(
            parser_ignore_whitespace(r"\b{ ").parse_escape().unwrap_err(),
            TestError {
                span: span(0..4),
                kind: ast::ErrorKind::SpecialWordOrRepetitionUnexpectedEof,
            }
        );
        // When 'x' is not enabled, the space is seen as a non-[-A-Za-z] char,
        // and thus causes the parser to treat it as a counted repetition.
        assert_eq!(
            parser(r"\b{ ").parse().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::RepetitionCountDecimalEmpty,
            }
        );
        // In this case, we got some valid chars that makes it look like the
        // user is writing one of the special word boundary assertions, but
        // we forget to close the brace.
        assert_eq!(
            parser(r"\b{foo").parse_escape().unwrap_err(),
            TestError {
                span: span(2..6),
                kind: ast::ErrorKind::SpecialWordBoundaryUnclosed,
            }
        );
        // We get the same error as above, except it is provoked by seeing a
        // char that we know is invalid before seeing a closing brace.
        assert_eq!(
            parser(r"\b{foo!}").parse_escape().unwrap_err(),
            TestError {
                span: span(2..6),
                kind: ast::ErrorKind::SpecialWordBoundaryUnclosed,
            }
        );
        // And this one occurs when, syntactically, everything looks okay, but
        // we don't use a valid spelling of a word boundary assertion.
        assert_eq!(
            parser(r"\b{foo}").parse_escape().unwrap_err(),
            TestError {
                span: span(3..6),
                kind: ast::ErrorKind::SpecialWordBoundaryUnrecognized,
            }
        );
        // An unfinished escape is illegal.
        assert_eq!(
            parser(r"\").parse_escape().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
    }
    #[test]
    fn parse_unsupported_backreference() {
        assert_eq!(
            parser(r"\0").parse_escape().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::UnsupportedBackreference,
            }
        );
        assert_eq!(
            parser(r"\9").parse_escape().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::UnsupportedBackreference,
            }
        );
    }
    #[test]
    fn parse_octal() {
        for i in 0..511 {
            let pat = format!(r"\{:o}", i);
            assert_eq!(
                parser_octal(&pat).parse_escape(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..pat.len()),
                    kind: ast::LiteralKind::Octal,
                    c: char::from_u32(i).unwrap(),
                }))
            );
        }
        assert_eq!(
            parser_octal(r"\778").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..3),
                kind: ast::LiteralKind::Octal,
                c: '?',
            }))
        );
        assert_eq!(
            parser_octal(r"\7777").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..4),
                kind: ast::LiteralKind::Octal,
                c: '\u{01FF}',
            }))
        );
        assert_eq!(
            parser_octal(r"\778").parse(),
            Ok(Ast::concat(ast::Concat {
                span: span(0..4),
                asts: vec![
                    Ast::literal(ast::Literal {
                        span: span(0..3),
                        kind: ast::LiteralKind::Octal,
                        c: '?',
                    }),
                    Ast::literal(ast::Literal {
                        span: span(3..4),
                        kind: ast::LiteralKind::Verbatim,
                        c: '8',
                    }),
                ],
            }))
        );
        assert_eq!(
            parser_octal(r"\7777").parse(),
            Ok(Ast::concat(ast::Concat {
                span: span(0..5),
                asts: vec![
                    Ast::literal(ast::Literal {
                        span: span(0..4),
                        kind: ast::LiteralKind::Octal,
                        c: '\u{01FF}',
                    }),
                    Ast::literal(ast::Literal {
                        span: span(4..5),
                        kind: ast::LiteralKind::Verbatim,
                        c: '7',
                    }),
                ],
            }))
        );
        assert_eq!(
            parser_octal(r"\8").parse_escape().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::EscapeUnrecognized,
            }
        );
    }
    #[test]
    fn parse_hex_two() {
        for i in 0..256 {
            let pat = format!(r"\x{:02x}", i);
            assert_eq!(
                parser(&pat).parse_escape(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..pat.len()),
                    kind: ast::LiteralKind::HexFixed(ast::HexLiteralKind::X),
                    c: char::from_u32(i).unwrap(),
                }))
            );
        }
        assert_eq!(
            parser(r"\xF").parse_escape().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\xG").parse_escape().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\xFG").parse_escape().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
    }
    #[test]
    fn parse_hex_four() {
        for i in 0..65536 {
            let c = match char::from_u32(i) {
                None => continue,
                Some(c) => c,
            };
            let pat = format!(r"\u{:04x}", i);
            assert_eq!(
                parser(&pat).parse_escape(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..pat.len()),
                    kind: ast::LiteralKind::HexFixed(
                        ast::HexLiteralKind::UnicodeShort
                    ),
                    c,
                }))
            );
        }
        assert_eq!(
            parser(r"\uF").parse_escape().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\uG").parse_escape().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\uFG").parse_escape().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\uFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\uFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(5..6),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\uD800").parse_escape().unwrap_err(),
            TestError {
                span: span(2..6),
                kind: ast::ErrorKind::EscapeHexInvalid,
            }
        );
    }
    #[test]
    fn parse_hex_eight() {
        for i in 0..65536 {
            let c = match char::from_u32(i) {
                None => continue,
                Some(c) => c,
            };
            let pat = format!(r"\U{:08x}", i);
            assert_eq!(
                parser(&pat).parse_escape(),
                Ok(Primitive::Literal(ast::Literal {
                    span: span(0..pat.len()),
                    kind: ast::LiteralKind::HexFixed(
                        ast::HexLiteralKind::UnicodeLong
                    ),
                    c,
                }))
            );
        }
        assert_eq!(
            parser(r"\UF").parse_escape().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\UG").parse_escape().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFG").parse_escape().unwrap_err(),
            TestError {
                span: span(3..4),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(5..6),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(6..7),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(7..8),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFFFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(8..9),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\UFFFFFFFG").parse_escape().unwrap_err(),
            TestError {
                span: span(9..10),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
    }
    #[test]
    fn parse_hex_brace() {
        assert_eq!(
            parser(r"\u{26c4}").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..8),
                kind: ast::LiteralKind::HexBrace(
                    ast::HexLiteralKind::UnicodeShort
                ),
                c: '⛄',
            }))
        );
        assert_eq!(
            parser(r"\U{26c4}").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..8),
                kind: ast::LiteralKind::HexBrace(
                    ast::HexLiteralKind::UnicodeLong
                ),
                c: '⛄',
            }))
        );
        assert_eq!(
            parser(r"\x{26c4}").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..8),
                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
                c: '⛄',
            }))
        );
        assert_eq!(
            parser(r"\x{26C4}").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..8),
                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
                c: '⛄',
            }))
        );
        assert_eq!(
            parser(r"\x{10fFfF}").parse_escape(),
            Ok(Primitive::Literal(ast::Literal {
                span: span(0..10),
                kind: ast::LiteralKind::HexBrace(ast::HexLiteralKind::X),
                c: '\u{10FFFF}',
            }))
        );
        assert_eq!(
            parser(r"\x").parse_escape().unwrap_err(),
            TestError {
                span: span(2..2),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\x{").parse_escape().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\x{FF").parse_escape().unwrap_err(),
            TestError {
                span: span(2..5),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\x{}").parse_escape().unwrap_err(),
            TestError {
                span: span(2..4),
                kind: ast::ErrorKind::EscapeHexEmpty,
            }
        );
        assert_eq!(
            parser(r"\x{FGF}").parse_escape().unwrap_err(),
            TestError {
                span: span(4..5),
                kind: ast::ErrorKind::EscapeHexInvalidDigit,
            }
        );
        assert_eq!(
            parser(r"\x{FFFFFF}").parse_escape().unwrap_err(),
            TestError {
                span: span(3..9),
                kind: ast::ErrorKind::EscapeHexInvalid,
            }
        );
        assert_eq!(
            parser(r"\x{D800}").parse_escape().unwrap_err(),
            TestError {
                span: span(3..7),
                kind: ast::ErrorKind::EscapeHexInvalid,
            }
        );
        assert_eq!(
            parser(r"\x{FFFFFFFFF}").parse_escape().unwrap_err(),
            TestError {
                span: span(3..12),
                kind: ast::ErrorKind::EscapeHexInvalid,
            }
        );
    }
    #[test]
    fn parse_decimal() {
        assert_eq!(parser("123").parse_decimal(), Ok(123));
        assert_eq!(parser("0").parse_decimal(), Ok(0));
        assert_eq!(parser("01").parse_decimal(), Ok(1));
        assert_eq!(
            parser("-1").parse_decimal().unwrap_err(),
            TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
        );
        assert_eq!(
            parser("").parse_decimal().unwrap_err(),
            TestError { span: span(0..0), kind: ast::ErrorKind::DecimalEmpty }
        );
        assert_eq!(
            parser("9999999999").parse_decimal().unwrap_err(),
            TestError {
                span: span(0..10),
                kind: ast::ErrorKind::DecimalInvalid,
            }
        );
    }
    #[test]
    fn parse_set_class() {
        fn union(span: Span, items: Vec<ast::ClassSetItem>) -> ast::ClassSet {
            ast::ClassSet::union(ast::ClassSetUnion { span, items })
        }
        fn intersection(
            span: Span,
            lhs: ast::ClassSet,
            rhs: ast::ClassSet,
        ) -> ast::ClassSet {
            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
                span,
                kind: ast::ClassSetBinaryOpKind::Intersection,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            })
        }
        fn difference(
            span: Span,
            lhs: ast::ClassSet,
            rhs: ast::ClassSet,
        ) -> ast::ClassSet {
            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
                span,
                kind: ast::ClassSetBinaryOpKind::Difference,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            })
        }
        fn symdifference(
            span: Span,
            lhs: ast::ClassSet,
            rhs: ast::ClassSet,
        ) -> ast::ClassSet {
            ast::ClassSet::BinaryOp(ast::ClassSetBinaryOp {
                span,
                kind: ast::ClassSetBinaryOpKind::SymmetricDifference,
                lhs: Box::new(lhs),
                rhs: Box::new(rhs),
            })
        }
        fn itemset(item: ast::ClassSetItem) -> ast::ClassSet {
            ast::ClassSet::Item(item)
        }
        fn item_ascii(cls: ast::ClassAscii) -> ast::ClassSetItem {
            ast::ClassSetItem::Ascii(cls)
        }
        fn item_unicode(cls: ast::ClassUnicode) -> ast::ClassSetItem {
            ast::ClassSetItem::Unicode(cls)
        }
        fn item_perl(cls: ast::ClassPerl) -> ast::ClassSetItem {
            ast::ClassSetItem::Perl(cls)
        }
        fn item_bracket(cls: ast::ClassBracketed) -> ast::ClassSetItem {
            ast::ClassSetItem::Bracketed(Box::new(cls))
        }
        fn lit(span: Span, c: char) -> ast::ClassSetItem {
            ast::ClassSetItem::Literal(ast::Literal {
                span,
                kind: ast::LiteralKind::Verbatim,
                c,
            })
        }
        fn empty(span: Span) -> ast::ClassSetItem {
            ast::ClassSetItem::Empty(span)
        }
        fn range(span: Span, start: char, end: char) -> ast::ClassSetItem {
            let pos1 = Position {
                offset: span.start.offset + start.len_utf8(),
                column: span.start.column + 1,
                ..span.start
            };
            let pos2 = Position {
                offset: span.end.offset - end.len_utf8(),
                column: span.end.column - 1,
                ..span.end
            };
            ast::ClassSetItem::Range(ast::ClassSetRange {
                span,
                start: ast::Literal {
                    span: Span { end: pos1, ..span },
                    kind: ast::LiteralKind::Verbatim,
                    c: start,
                },
                end: ast::Literal {
                    span: Span { start: pos2, ..span },
                    kind: ast::LiteralKind::Verbatim,
                    c: end,
                },
            })
        }
        fn alnum(span: Span, negated: bool) -> ast::ClassAscii {
            ast::ClassAscii { span, kind: ast::ClassAsciiKind::Alnum, negated }
        }
        fn lower(span: Span, negated: bool) -> ast::ClassAscii {
            ast::ClassAscii { span, kind: ast::ClassAsciiKind::Lower, negated }
        }
        assert_eq!(
            parser("[[:alnum:]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..11),
                negated: false,
                kind: itemset(item_ascii(alnum(span(1..10), false))),
            }))
        );
        assert_eq!(
            parser("[[[:alnum:]]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..13),
                negated: false,
                kind: itemset(item_bracket(ast::ClassBracketed {
                    span: span(1..12),
                    negated: false,
                    kind: itemset(item_ascii(alnum(span(2..11), false))),
                })),
            }))
        );
        assert_eq!(
            parser("[[:alnum:]&&[:lower:]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..22),
                negated: false,
                kind: intersection(
                    span(1..21),
                    itemset(item_ascii(alnum(span(1..10), false))),
                    itemset(item_ascii(lower(span(12..21), false))),
                ),
            }))
        );
        assert_eq!(
            parser("[[:alnum:]--[:lower:]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..22),
                negated: false,
                kind: difference(
                    span(1..21),
                    itemset(item_ascii(alnum(span(1..10), false))),
                    itemset(item_ascii(lower(span(12..21), false))),
                ),
            }))
        );
        assert_eq!(
            parser("[[:alnum:]~~[:lower:]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..22),
                negated: false,
                kind: symdifference(
                    span(1..21),
                    itemset(item_ascii(alnum(span(1..10), false))),
                    itemset(item_ascii(lower(span(12..21), false))),
                ),
            }))
        );
        assert_eq!(
            parser("[a]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..3),
                negated: false,
                kind: itemset(lit(span(1..2), 'a')),
            }))
        );
        assert_eq!(
            parser(r"[a\]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..5),
                negated: false,
                kind: union(
                    span(1..4),
                    vec![
                        lit(span(1..2), 'a'),
                        ast::ClassSetItem::Literal(ast::Literal {
                            span: span(2..4),
                            kind: ast::LiteralKind::Meta,
                            c: ']',
                        }),
                    ]
                ),
            }))
        );
        assert_eq!(
            parser(r"[a\-z]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..6),
                negated: false,
                kind: union(
                    span(1..5),
                    vec![
                        lit(span(1..2), 'a'),
                        ast::ClassSetItem::Literal(ast::Literal {
                            span: span(2..4),
                            kind: ast::LiteralKind::Meta,
                            c: '-',
                        }),
                        lit(span(4..5), 'z'),
                    ]
                ),
            }))
        );
        assert_eq!(
            parser("[ab]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..4),
                negated: false,
                kind: union(
                    span(1..3),
                    vec![lit(span(1..2), 'a'), lit(span(2..3), 'b'),]
                ),
            }))
        );
        assert_eq!(
            parser("[a-]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..4),
                negated: false,
                kind: union(
                    span(1..3),
                    vec![lit(span(1..2), 'a'), lit(span(2..3), '-'),]
                ),
            }))
        );
        assert_eq!(
            parser("[-a]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..4),
                negated: false,
                kind: union(
                    span(1..3),
                    vec![lit(span(1..2), '-'), lit(span(2..3), 'a'),]
                ),
            }))
        );
        assert_eq!(
            parser(r"[\pL]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..5),
                negated: false,
                kind: itemset(item_unicode(ast::ClassUnicode {
                    span: span(1..4),
                    negated: false,
                    kind: ast::ClassUnicodeKind::OneLetter('L'),
                })),
            }))
        );
        assert_eq!(
            parser(r"[\w]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..4),
                negated: false,
                kind: itemset(item_perl(ast::ClassPerl {
                    span: span(1..3),
                    kind: ast::ClassPerlKind::Word,
                    negated: false,
                })),
            }))
        );
        assert_eq!(
            parser(r"[a\wz]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..6),
                negated: false,
                kind: union(
                    span(1..5),
                    vec![
                        lit(span(1..2), 'a'),
                        item_perl(ast::ClassPerl {
                            span: span(2..4),
                            kind: ast::ClassPerlKind::Word,
                            negated: false,
                        }),
                        lit(span(4..5), 'z'),
                    ]
                ),
            }))
        );
        assert_eq!(
            parser("[a-z]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..5),
                negated: false,
                kind: itemset(range(span(1..4), 'a', 'z')),
            }))
        );
        assert_eq!(
            parser("[a-cx-z]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..8),
                negated: false,
                kind: union(
                    span(1..7),
                    vec![
                        range(span(1..4), 'a', 'c'),
                        range(span(4..7), 'x', 'z'),
                    ]
                ),
            }))
        );
        assert_eq!(
            parser(r"[\w&&a-cx-z]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..12),
                negated: false,
                kind: intersection(
                    span(1..11),
                    itemset(item_perl(ast::ClassPerl {
                        span: span(1..3),
                        kind: ast::ClassPerlKind::Word,
                        negated: false,
                    })),
                    union(
                        span(5..11),
                        vec![
                            range(span(5..8), 'a', 'c'),
                            range(span(8..11), 'x', 'z'),
                        ]
                    ),
                ),
            }))
        );
        assert_eq!(
            parser(r"[a-cx-z&&\w]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..12),
                negated: false,
                kind: intersection(
                    span(1..11),
                    union(
                        span(1..7),
                        vec![
                            range(span(1..4), 'a', 'c'),
                            range(span(4..7), 'x', 'z'),
                        ]
                    ),
                    itemset(item_perl(ast::ClassPerl {
                        span: span(9..11),
                        kind: ast::ClassPerlKind::Word,
                        negated: false,
                    })),
                ),
            }))
        );
        assert_eq!(
            parser(r"[a--b--c]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..9),
                negated: false,
                kind: difference(
                    span(1..8),
                    difference(
                        span(1..5),
                        itemset(lit(span(1..2), 'a')),
                        itemset(lit(span(4..5), 'b')),
                    ),
                    itemset(lit(span(7..8), 'c')),
                ),
            }))
        );
        assert_eq!(
            parser(r"[a~~b~~c]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..9),
                negated: false,
                kind: symdifference(
                    span(1..8),
                    symdifference(
                        span(1..5),
                        itemset(lit(span(1..2), 'a')),
                        itemset(lit(span(4..5), 'b')),
                    ),
                    itemset(lit(span(7..8), 'c')),
                ),
            }))
        );
        assert_eq!(
            parser(r"[\^&&^]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..7),
                negated: false,
                kind: intersection(
                    span(1..6),
                    itemset(ast::ClassSetItem::Literal(ast::Literal {
                        span: span(1..3),
                        kind: ast::LiteralKind::Meta,
                        c: '^',
                    })),
                    itemset(lit(span(5..6), '^')),
                ),
            }))
        );
        assert_eq!(
            parser(r"[\&&&&]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..7),
                negated: false,
                kind: intersection(
                    span(1..6),
                    itemset(ast::ClassSetItem::Literal(ast::Literal {
                        span: span(1..3),
                        kind: ast::LiteralKind::Meta,
                        c: '&',
                    })),
                    itemset(lit(span(5..6), '&')),
                ),
            }))
        );
        assert_eq!(
            parser(r"[&&&&]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..6),
                negated: false,
                kind: intersection(
                    span(1..5),
                    intersection(
                        span(1..3),
                        itemset(empty(span(1..1))),
                        itemset(empty(span(3..3))),
                    ),
                    itemset(empty(span(5..5))),
                ),
            }))
        );
        let pat = "[☃-⛄]";
        assert_eq!(
            parser(pat).parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span_range(pat, 0..9),
                negated: false,
                kind: itemset(ast::ClassSetItem::Range(ast::ClassSetRange {
                    span: span_range(pat, 1..8),
                    start: ast::Literal {
                        span: span_range(pat, 1..4),
                        kind: ast::LiteralKind::Verbatim,
                        c: '☃',
                    },
                    end: ast::Literal {
                        span: span_range(pat, 5..8),
                        kind: ast::LiteralKind::Verbatim,
                        c: '⛄',
                    },
                })),
            }))
        );
        assert_eq!(
            parser(r"[]]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..3),
                negated: false,
                kind: itemset(lit(span(1..2), ']')),
            }))
        );
        assert_eq!(
            parser(r"[]\[]").parse(),
            Ok(Ast::class_bracketed(ast::ClassBracketed {
                span: span(0..5),
                negated: false,
                kind: union(
                    span(1..4),
                    vec![
                        lit(span(1..2), ']'),
                        ast::ClassSetItem::Literal(ast::Literal {
                            span: span(2..4),
                            kind: ast::LiteralKind::Meta,
                            c: '[',
                        }),
                    ]
                ),
            }))
        );
        assert_eq!(
            parser(r"[\[]]").parse(),
            Ok(concat(
                0..5,
                vec![
                    Ast::class_bracketed(ast::ClassBracketed {
                        span: span(0..4),
                        negated: false,
                        kind: itemset(ast::ClassSetItem::Literal(
                            ast::Literal {
                                span: span(1..3),
                                kind: ast::LiteralKind::Meta,
                                c: '[',
                            }
                        )),
                    }),
                    Ast::literal(ast::Literal {
                        span: span(4..5),
                        kind: ast::LiteralKind::Verbatim,
                        c: ']',
                    }),
                ]
            ))
        );
        assert_eq!(
            parser("[").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[[").parse().unwrap_err(),
            TestError {
                span: span(1..2),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[[-]").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[[[:alnum:]").parse().unwrap_err(),
            TestError {
                span: span(1..2),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser(r"[\b]").parse().unwrap_err(),
            TestError {
                span: span(1..3),
                kind: ast::ErrorKind::ClassEscapeInvalid,
            }
        );
        assert_eq!(
            parser(r"[\w-a]").parse().unwrap_err(),
            TestError {
                span: span(1..3),
                kind: ast::ErrorKind::ClassRangeLiteral,
            }
        );
        assert_eq!(
            parser(r"[a-\w]").parse().unwrap_err(),
            TestError {
                span: span(3..5),
                kind: ast::ErrorKind::ClassRangeLiteral,
            }
        );
        assert_eq!(
            parser(r"[z-a]").parse().unwrap_err(),
            TestError {
                span: span(1..4),
                kind: ast::ErrorKind::ClassRangeInvalid,
            }
        );
        assert_eq!(
            parser_ignore_whitespace("[a ").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser_ignore_whitespace("[a- ").parse().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
    }
    #[test]
    fn parse_set_class_open() {
        assert_eq!(parser("[a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..1),
                negated: false,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(1..1),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion { span: span(1..1), items: vec![] };
            Ok((set, union))
        });
        assert_eq!(
            parser_ignore_whitespace("[   a]").parse_set_class_open(),
            {
                let set = ast::ClassBracketed {
                    span: span(0..4),
                    negated: false,
                    kind: ast::ClassSet::union(ast::ClassSetUnion {
                        span: span(4..4),
                        items: vec![],
                    }),
                };
                let union =
                    ast::ClassSetUnion { span: span(4..4), items: vec![] };
                Ok((set, union))
            }
        );
        assert_eq!(parser("[^a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..2),
                negated: true,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(2..2),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion { span: span(2..2), items: vec![] };
            Ok((set, union))
        });
        assert_eq!(
            parser_ignore_whitespace("[ ^ a]").parse_set_class_open(),
            {
                let set = ast::ClassBracketed {
                    span: span(0..4),
                    negated: true,
                    kind: ast::ClassSet::union(ast::ClassSetUnion {
                        span: span(4..4),
                        items: vec![],
                    }),
                };
                let union =
                    ast::ClassSetUnion { span: span(4..4), items: vec![] };
                Ok((set, union))
            }
        );
        assert_eq!(parser("[-a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..2),
                negated: false,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(1..1),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(1..2),
                items: vec![ast::ClassSetItem::Literal(ast::Literal {
                    span: span(1..2),
                    kind: ast::LiteralKind::Verbatim,
                    c: '-',
                })],
            };
            Ok((set, union))
        });
        assert_eq!(
            parser_ignore_whitespace("[ - a]").parse_set_class_open(),
            {
                let set = ast::ClassBracketed {
                    span: span(0..4),
                    negated: false,
                    kind: ast::ClassSet::union(ast::ClassSetUnion {
                        span: span(2..2),
                        items: vec![],
                    }),
                };
                let union = ast::ClassSetUnion {
                    span: span(2..3),
                    items: vec![ast::ClassSetItem::Literal(ast::Literal {
                        span: span(2..3),
                        kind: ast::LiteralKind::Verbatim,
                        c: '-',
                    })],
                };
                Ok((set, union))
            }
        );
        assert_eq!(parser("[^-a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..3),
                negated: true,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(2..2),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(2..3),
                items: vec![ast::ClassSetItem::Literal(ast::Literal {
                    span: span(2..3),
                    kind: ast::LiteralKind::Verbatim,
                    c: '-',
                })],
            };
            Ok((set, union))
        });
        assert_eq!(parser("[--a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..3),
                negated: false,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(1..1),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(1..3),
                items: vec![
                    ast::ClassSetItem::Literal(ast::Literal {
                        span: span(1..2),
                        kind: ast::LiteralKind::Verbatim,
                        c: '-',
                    }),
                    ast::ClassSetItem::Literal(ast::Literal {
                        span: span(2..3),
                        kind: ast::LiteralKind::Verbatim,
                        c: '-',
                    }),
                ],
            };
            Ok((set, union))
        });
        assert_eq!(parser("[]a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..2),
                negated: false,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(1..1),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(1..2),
                items: vec![ast::ClassSetItem::Literal(ast::Literal {
                    span: span(1..2),
                    kind: ast::LiteralKind::Verbatim,
                    c: ']',
                })],
            };
            Ok((set, union))
        });
        assert_eq!(
            parser_ignore_whitespace("[ ] a]").parse_set_class_open(),
            {
                let set = ast::ClassBracketed {
                    span: span(0..4),
                    negated: false,
                    kind: ast::ClassSet::union(ast::ClassSetUnion {
                        span: span(2..2),
                        items: vec![],
                    }),
                };
                let union = ast::ClassSetUnion {
                    span: span(2..3),
                    items: vec![ast::ClassSetItem::Literal(ast::Literal {
                        span: span(2..3),
                        kind: ast::LiteralKind::Verbatim,
                        c: ']',
                    })],
                };
                Ok((set, union))
            }
        );
        assert_eq!(parser("[^]a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..3),
                negated: true,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(2..2),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(2..3),
                items: vec![ast::ClassSetItem::Literal(ast::Literal {
                    span: span(2..3),
                    kind: ast::LiteralKind::Verbatim,
                    c: ']',
                })],
            };
            Ok((set, union))
        });
        assert_eq!(parser("[-]a]").parse_set_class_open(), {
            let set = ast::ClassBracketed {
                span: span(0..2),
                negated: false,
                kind: ast::ClassSet::union(ast::ClassSetUnion {
                    span: span(1..1),
                    items: vec![],
                }),
            };
            let union = ast::ClassSetUnion {
                span: span(1..2),
                items: vec![ast::ClassSetItem::Literal(ast::Literal {
                    span: span(1..2),
                    kind: ast::LiteralKind::Verbatim,
                    c: '-',
                })],
            };
            Ok((set, union))
        });
        assert_eq!(
            parser("[").parse_set_class_open().unwrap_err(),
            TestError {
                span: span(0..1),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser_ignore_whitespace("[    ")
                .parse_set_class_open()
                .unwrap_err(),
            TestError {
                span: span(0..5),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[^").parse_set_class_open().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[]").parse_set_class_open().unwrap_err(),
            TestError {
                span: span(0..2),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[-").parse_set_class_open().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        assert_eq!(
            parser("[--").parse_set_class_open().unwrap_err(),
            TestError {
                span: span(0..0),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
        // See: https://github.com/rust-lang/regex/issues/792
        assert_eq!(
            parser("(?x)[-#]").parse_with_comments().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::ClassUnclosed,
            }
        );
    }
    #[test]
    fn maybe_parse_ascii_class() {
        assert_eq!(
            parser(r"[:alnum:]").maybe_parse_ascii_class(),
            Some(ast::ClassAscii {
                span: span(0..9),
                kind: ast::ClassAsciiKind::Alnum,
                negated: false,
            })
        );
        assert_eq!(
            parser(r"[:alnum:]A").maybe_parse_ascii_class(),
            Some(ast::ClassAscii {
                span: span(0..9),
                kind: ast::ClassAsciiKind::Alnum,
                negated: false,
            })
        );
        assert_eq!(
            parser(r"[:^alnum:]").maybe_parse_ascii_class(),
            Some(ast::ClassAscii {
                span: span(0..10),
                kind: ast::ClassAsciiKind::Alnum,
                negated: true,
            })
        );
        let p = parser(r"[:");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
        let p = parser(r"[:^");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
        let p = parser(r"[^:alnum:]");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
        let p = parser(r"[:alnnum:]");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
        let p = parser(r"[:alnum]");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
        let p = parser(r"[:alnum:");
        assert_eq!(p.maybe_parse_ascii_class(), None);
        assert_eq!(p.offset(), 0);
    }
    #[test]
    fn parse_unicode_class() {
        assert_eq!(
            parser(r"\pN").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..3),
                negated: false,
                kind: ast::ClassUnicodeKind::OneLetter('N'),
            }))
        );
        assert_eq!(
            parser(r"\PN").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..3),
                negated: true,
                kind: ast::ClassUnicodeKind::OneLetter('N'),
            }))
        );
        assert_eq!(
            parser(r"\p{N}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..5),
                negated: false,
                kind: ast::ClassUnicodeKind::Named(s("N")),
            }))
        );
        assert_eq!(
            parser(r"\P{N}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..5),
                negated: true,
                kind: ast::ClassUnicodeKind::Named(s("N")),
            }))
        );
        assert_eq!(
            parser(r"\p{Greek}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..9),
                negated: false,
                kind: ast::ClassUnicodeKind::Named(s("Greek")),
            }))
        );
        assert_eq!(
            parser(r"\p{scx:Katakana}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..16),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::Colon,
                    name: s("scx"),
                    value: s("Katakana"),
                },
            }))
        );
        assert_eq!(
            parser(r"\p{scx=Katakana}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..16),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::Equal,
                    name: s("scx"),
                    value: s("Katakana"),
                },
            }))
        );
        assert_eq!(
            parser(r"\p{scx!=Katakana}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..17),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::NotEqual,
                    name: s("scx"),
                    value: s("Katakana"),
                },
            }))
        );
        assert_eq!(
            parser(r"\p{:}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..5),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::Colon,
                    name: s(""),
                    value: s(""),
                },
            }))
        );
        assert_eq!(
            parser(r"\p{=}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..5),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::Equal,
                    name: s(""),
                    value: s(""),
                },
            }))
        );
        assert_eq!(
            parser(r"\p{!=}").parse_escape(),
            Ok(Primitive::Unicode(ast::ClassUnicode {
                span: span(0..6),
                negated: false,
                kind: ast::ClassUnicodeKind::NamedValue {
                    op: ast::ClassUnicodeOpKind::NotEqual,
                    name: s(""),
                    value: s(""),
                },
            }))
        );
        assert_eq!(
            parser(r"\p").parse_escape().unwrap_err(),
            TestError {
                span: span(2..2),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\p{").parse_escape().unwrap_err(),
            TestError {
                span: span(3..3),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\p{N").parse_escape().unwrap_err(),
            TestError {
                span: span(4..4),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\p{Greek").parse_escape().unwrap_err(),
            TestError {
                span: span(8..8),
                kind: ast::ErrorKind::EscapeUnexpectedEof,
            }
        );
        assert_eq!(
            parser(r"\pNz").parse(),
            Ok(Ast::concat(ast::Concat {
                span: span(0..4),
                asts: vec![
                    Ast::class_unicode(ast::ClassUnicode {
                        span: span(0..3),
                        negated: false,
                        kind: ast::ClassUnicodeKind::OneLetter('N'),
                    }),
                    Ast::literal(ast::Literal {
                        span: span(3..4),
                        kind: ast::LiteralKind::Verbatim,
                        c: 'z',
                    }),
                ],
            }))
        );
        assert_eq!(
            parser(r"\p{Greek}z").parse(),
            Ok(Ast::concat(ast::Concat {
                span: span(0..10),
                asts: vec![
                    Ast::class_unicode(ast::ClassUnicode {
                        span: span(0..9),
                        negated: false,
                        kind: ast::ClassUnicodeKind::Named(s("Greek")),
                    }),
                    Ast::literal(ast::Literal {
                        span: span(9..10),
                        kind: ast::LiteralKind::Verbatim,
                        c: 'z',
                    }),
                ],
            }))
        );
        assert_eq!(
            parser(r"\p\{").parse().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::UnicodeClassInvalid,
            }
        );
        assert_eq!(
            parser(r"\P\{").parse().unwrap_err(),
            TestError {
                span: span(2..3),
                kind: ast::ErrorKind::UnicodeClassInvalid,
            }
        );
    }
    #[test]
    fn parse_perl_class() {
        assert_eq!(
            parser(r"\d").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Digit,
                negated: false,
            }))
        );
        assert_eq!(
            parser(r"\D").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Digit,
                negated: true,
            }))
        );
        assert_eq!(
            parser(r"\s").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Space,
                negated: false,
            }))
        );
        assert_eq!(
            parser(r"\S").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Space,
                negated: true,
            }))
        );
        assert_eq!(
            parser(r"\w").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Word,
                negated: false,
            }))
        );
        assert_eq!(
            parser(r"\W").parse_escape(),
            Ok(Primitive::Perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Word,
                negated: true,
            }))
        );
        assert_eq!(
            parser(r"\d").parse(),
            Ok(Ast::class_perl(ast::ClassPerl {
                span: span(0..2),
                kind: ast::ClassPerlKind::Digit,
                negated: false,
            }))
        );
        assert_eq!(
            parser(r"\dz").parse(),
            Ok(Ast::concat(ast::Concat {
                span: span(0..3),
                asts: vec![
                    Ast::class_perl(ast::ClassPerl {
                        span: span(0..2),
                        kind: ast::ClassPerlKind::Digit,
                        negated: false,
                    }),
                    Ast::literal(ast::Literal {
                        span: span(2..3),
                        kind: ast::LiteralKind::Verbatim,
                        c: 'z',
                    }),
                ],
            }))
        );
    }
    // This tests a bug fix where the nest limit checker wasn't decrementing
    // its depth during post-traversal, which causes long regexes to trip
    // the default limit too aggressively.
    #[test]
    fn regression_454_nest_too_big() {
        let pattern = r#"
        2(?:
          [45]\d{3}|
          7(?:
            1[0-267]|
            2[0-289]|
            3[0-29]|
            4[01]|
            5[1-3]|
            6[013]|
            7[0178]|
            91
          )|
          8(?:
            0[125]|
            [139][1-6]|
            2[0157-9]|
            41|
            6[1-35]|
            7[1-5]|
            8[1-8]|
            90
          )|
          9(?:
            0[0-2]|
            1[0-4]|
            2[568]|
            3[3-6]|
            5[5-7]|
            6[0167]|
            7[15]|
            8[0146-9]
          )
        )\d{4}
        "#;
        assert!(parser_nest_limit(pattern, 50).parse().is_ok());
    }
    // This tests that we treat a trailing `-` in a character class as a
    // literal `-` even when whitespace mode is enabled and there is whitespace
    // after the trailing `-`.
    #[test]
    fn regression_455_trailing_dash_ignore_whitespace() {
        assert!(parser("(?x)[ / - ]").parse().is_ok());
        assert!(parser("(?x)[ a - ]").parse().is_ok());
        assert!(parser(
            "(?x)[
            a
            - ]
        "
        )
        .parse()
        .is_ok());
        assert!(parser(
            "(?x)[
            a # wat
            - ]
        "
        )
        .parse()
        .is_ok());
        assert!(parser("(?x)[ / -").parse().is_err());
        assert!(parser("(?x)[ / - ").parse().is_err());
        assert!(parser(
            "(?x)[
            / -
        "
        )
        .parse()
        .is_err());
        assert!(parser(
            "(?x)[
            / - # wat
        "
        )
        .parse()
        .is_err());
    }
}